how to get the path from root to a given node on a binary tree?_问答_开发者

I am trying to find out how to get the path from root to a given node on a binary tree.

It is not binary search tree.

Each non-leaf node has only two pointers to their children.

In-order, pre-order, post-order traversal do not work.

I have tried to do pre-order but cannot figure out how. For example, we have a binary tree: It is NOT a binary search tree. We use the sorting order node to make it easier to find the path.

     1 
   /   \
  2     3
 / \   / \
4   5 6   7

We want开发者_高级运维 to find the path from 1 to 7:

With pre-order, we have:

1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7

From the flow, we get the path from 1 -> 7 with all nodes on it.

Obviuosly, it should not be.

Any help is really appreciated.

Preorder traversal, otherwise known as depth-first search does work.

If you implement preorder traversal recursively, then when you reach the desired node, you can unwind your stack (of recursive calls) and construct your path in reverse.
If you implement the preorder traversal non-recursively, then you will be building a stack directly, so in this case once you reach your desired node you have your path already.

In the tree in your question above, the algorithm to find the path from 1 to 7 proceeds as follows.

Start with 1, push it on the stack, stack is now [1]
Go left to the 2, push it on the stack, stack is now [1 2]
Go left to the 4, push it, stack is now [1 2 4]
There are no children of 4, and it is not what you want, so pop it, stack is now [1 2]
Now that you are back at the 2, and you have already gone left, now go right, stack is now [1 2 5]
There are no children of 5, so pop, stack is now [1 2]
You have exhausted the children of 2, so pop it, stack is now [1]
Now you are back at the 1 and you have finished the left, so go right to the 3, push it, stack is now [1 3]
Go left, stack is now [1 3 6]
6 is a leaf, not what you are looking for, so pop, stack is [1 3]
Now you have to go to the right from 3, push it, stack is now [1 3 7]
But WAIT! LOOK! You have arrived at the node you are looking for! And look at your stack! It's the path you want.

You are given a binary tree ( root Node) .. and a key is given which may or may not be in the tree. You have to find the full path from the root to the node.

Example:

                A
           /           \
       B                C
         \               /
          D           E
        /    \           \
      K      L        M
    /
Z

you have given node Z ( or the key for the Node ) and given Node A( root) So your output should be

A B D K Z

if M is given, the output should be A C E M

public class main_class {
public static void main(String args[] ) {

    //first create tree
    Node rootNode = new Node ('A' , new Node('B',null,
                                             new Node('D',
                                                      new Node('K',
                                                               new Node('Z',null,
                                                               null),null),
                                                      new Node('L',null,null))),
                                    new Node('C',
                                             new Node('E',
                                                      null,
                                                      new Node('M',null,null)),null) );

    ArrayList <Node> path = new ArrayList<Node>();
    System.out.println(getPath(rootNode,'Z',path));
    System.out.println(path);
    path = new ArrayList<Node>();
    System.out.println(getPath(rootNode,'M',path));
    System.out.println(path);

}
static boolean getPath(Node rootNode, char key, ArrayList<Node> path ){
    //return true if the node is found
    if( rootNode==null)
        return false;
    if (rootNode.getVal()==key){
        path.add(rootNode);
        return true;
    }
    boolean left_check = getPath( rootNode.left,key,path);
    boolean right_check = getPath( rootNode.right,key,path);
    if ( left_check || right_check){
        path.add(rootNode);
        return true;
    }
    return false;

}
static class Node {
    char val;
    Node left;
    Node right;
    public Node( char val, Node left, Node right){
        this.left=left;
        this.right=right;
        this.val=val;
    }
    public char getVal(){
        return val;
    }
   public String toString(){
        return " " + val + " ";
    }
}

}

Consider the following tree:

Approach

We start from the root and compare it with the key, if they matched then print the path (if the tree has just one node then the path contains just the root).
Else push the node into Vector (I considered vector for storing the path).
Recursively Go left and right of the tree.

The following code will help:

     void PrintPath(node* root, vector <int> v,int key)
     {
      if(!root)
      return;
      if(root->data==key)
        {
          v.push_back(root->data);
          vector<int>:: iterator it;
          for(it=v.begin();it<v.end();it++)
           {
             cout<<*it<<" ";
           }
            return;
        }
        v.push_back(root->data);
        PrintPath(root->left,v,key);
        PrintPath(root->right,v,key);
    }

Explanation

Let the node to be found be 5(key) for the given tree.

Contents of vector at each step:

V = 10
V = 10,8
V = 10,8,3 (3 is not the key to be found, so we will backtrack and go to right)
V = 10,8,5 (5 is the key therefore print the Path).

There are 3 solutions here in Java:
https://codereview.stackexchange.com/questions/105136/path-sum-in-binary-tree
First, recursive approach, second one by using 2 satcks, and last one by using 2 queues. Hope this helps

public List<Node<T>> getPath(T data){
        Stack<Node<T>> stack = new Stack<Node<T>>();
        Boolean found =  getPath(root, stack, data);
        List<Node<T>> path = new ArrayList<Node<T>>();

        if(!found){
            return path;
        }
        return Arrays.asList(stack.toArray((Node<T>[])new Node[stack.size()]));
    }

    public Boolean getPath(Node<T> node, Stack<Node<T>> stack, T data){
        if(node == null){
            return false;
        }
        stack.push(node);

        if(node.data.equals(data)){
            return true;
        }
        Boolean found = getPath(node.left, stack, data) ||
                getPath(node.right, stack, data);

        if(!found ){
            stack.pop();
        }
        return found;
    }