Given a binary tree, a target node in the binary tree, and an integer value k, print all the nodes that are at distance k from the given target node. No parent pointers are available.
Consider the tree shown in diagram Input: target = pointer to node with data 8. root = pointer to node with data 20. k = 2. Output : 10 14 22 If target is 14 and k is 3, then output should be "4 20"
There are two types of nodes to be considered.
1) Nodes in the subtree rooted with target node. For example if the target node is 8 and k is 2, then such nodes are 10 and 14.
2) Other nodes, may be an ancestor of target, or a node in some other subtree. For target node 8 and k is 2, the node 22 comes in this category.
Finding the first type of nodes is easy to implement. Just traverse subtrees rooted with the target node and decrement k in recursive call. When the k becomes 0, print the node currently being traversed (See this for more details). Here we call the function as printkdistanceNodeDown().
How to find nodes of second type? For the output nodes not lying in the subtree with the target node as the root, we must go through all ancestors. For every ancestor, we find its distance from target node, let the distance be d, now we go to other subtree (if target was found in left subtree, then we go to right subtree and vice versa) of the ancestor and find all nodes at k-d distance from the ancestor.
Following is C++ implementation of the above approach.
#include <iostream> using namespace std; // A binary Tree node struct node { int data; struct node *left, *right; }; /* Recursive function to print all the nodes at distance k in the tree (or subtree) rooted with given root. See */ void printkdistanceNodeDown(node *root, int k) { // Base Case if (root == NULL || k < 0) return; // If we reach a k distant node, print it if (k==0) { cout << root->data << endl; return; } // Recur for left and right subtrees printkdistanceNodeDown(root->left, k-1); printkdistanceNodeDown(root->right, k-1); } // Prints all nodes at distance k from a given target node. // The k distant nodes may be upward or downward. This function // Returns distance of root from target node, it returns -1 if target // node is not present in tree rooted with root. int printkdistanceNode(node* root, node* target , int k) { // Base Case 1: If tree is empty, return -1 if (root == NULL) return -1; // If target is same as root. Use the downward function // to print all nodes at distance k in subtree rooted with // target or root if (root == target) { printkdistanceNodeDown(root, k); return 0; } // Recur for left subtree int dl = printkdistanceNode(root->left, target, k); // Check if target node was found in left subtree if (dl != -1) { // If root is at distance k from target, print root // Note that dl is Distance of root's left child from target if (dl + 1 == k) cout << root->data << endl; // Else go to right subtree and print all k-dl-2 distant nodes // Note that the right child is 2 edges away from left child else printkdistanceNodeDown(root->right, k-dl-2); // Add 1 to the distance and return value for parent calls return 1 + dl; } // MIRROR OF ABOVE CODE FOR RIGHT SUBTREE // Note that we reach here only when node was not found in left subtree int dr = printkdistanceNode(root->right, target, k); if (dr != -1) { if (dr + 1 == k) cout << root->data << endl; else printkdistanceNodeDown(root->left, k-dr-2); return 1 + dr; } // If target was neither present in left nor in right subtree return -1; }
Time Complexity: At first look the time complexity looks more than O(n), but if we take a closer look, we can observe that no node is traversed more than twice. Therefore the time complexity is O(n).
From:
http://www.geeksforgeeks.org/print-nodes-distance-k-given-node-binary-tree/
相关推荐
路由选路算法距离向量算法的编程实现,c
At a given time, several nodes transmit simultaneously, each toward its own receiver. Each transmitter–receiver pair requires its own wireless link. The signal received from the link transmitter may...
At a given time, several nodes transmit simultaneously, each toward its own receiver. Each transmitter–receiver pair requires its own wireless link. The signal received from the link transmitter may...
mldonkey需要的nodes.dat
item, and storing the key/data item pair at the node to which the an Æ -node system, each node maintains information only about key maps. Chord adapts efficiently as nodes join and leave the Ç ́...
It can be executed from the references node, a single reference node or set of reference nodes. Paste References This command pastes a reference or set of references from the clipboard. It can be ...
a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layerwise thus exploring the neighbour nodes. - We start from a node and ...
更新节点更新推荐的Node.js版本注意: 是必需的快速概述npx update-nodes安装npm i -g update-nodes有关的
无线传感器网络随机分布节点,形成拓扑结构
Allowing a node to encode it received data before passing it on, the question involves optimizaion of the multicast mechanisms at the nodes. Among the simples coding schemes is linear coding, which ...
streaming architecture at all stages of kd-tree construction. Unlike previous parallel kd-tree algorithms, our method builds tree nodes completely in BFS (breadth-first search) order. We also develop ...
signed distance from each node location p to the closest boundary. • The desired edge length function h is given as a function fh, which returns h for all input points. • The parameter h0 is the ...
安装$ npm install worker-nodes 需要大于11.7.0的Node.jsAPI参考工作节点种类:全球舱 : Proxy ⇒ Promise ⇒ Promise ⇒ void ⇒ void ⇒ Array.新的WorkerNodes(路径,[选项]) 参数类型描述路径String 将在...
signed distance from each node location p to the closest boundary. • The desired edge length function h is given as a function fh, which returns h for all input points. • The parameter h0 is the ...
signed distance from each node location p to the closest boundary. • The desired edge length function h is given as a function fh, which returns h for all input points. • The parameter h0 is the ...
signed distance from each node location p to the closest boundary. • The desired edge length function h is given as a function fh, which returns h for all input points. • The parameter h0 is the ...
The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than or equal to the node's key. Both the left ...
Create Tests Node: assigns a set of tests from a test schedule to a sample. Action Node: Defines a branch of the workflow that will be executed in response to a user action. Event Node: Defines a ...
The active node measures the time delay between the acoustic signal it sends and the acoustic signal received from the target node and then, taking into account the extra time delay caused by signal ...
The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than or equal to the node's key. Both the left and ...