如何获取从根到二叉树上给定节点的路径？

Question

我试图找出如何获取从二进制树上的根到给定节点的路径.

它不是二叉搜索树.

每个非叶子节点只有两个指向其子节点的指针.

按顺序,预订,后订单遍历不起作用.

我曾尝试做预购,但无法弄清楚如何.例如,我们有一个二叉树:它不是二叉搜索树.我们使用排序顺序节点来更容易地找到路径.

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

我们想要找到1到7的路径:

通过预购,我们有:

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

从流程中,我们得到路径从1 - > 7,其上包含所有节点.

显然,它不应该.

任何帮助都非常感谢.

Answer 1

预订遍历,也称为深度优先搜索确实有效.

• 如果以递归方式实现preorder遍历,那么当到达所需节点时,可以展开堆栈(递归调用)并反向构建路径.

• 如果您以非递归方式实现前序遍历,那么您将直接构建一个堆栈,因此在这种情况下,一旦到达所需的节点,您就已经拥有了路径.

在上面问题的树中,查找从1到7的路径的算法如下所示.

• 从1开始,将其推入堆栈,现在堆栈为[1]
• 向左移动到2,将其推入堆栈,堆栈现在为[1 2]
• 左转到4,推它,现在堆栈[1 2 4]
• 没有4岁的孩子,这不是你想要的,所以弹出它,叠现在[1 2]
• 现在你回到了2,你已经离开了,现在走吧,堆栈现在是[1 2 5]
• 没有5个孩子,所以pop,stack现在是[1 2]
• 你已经筋疲力尽2的孩子,所以弹出它,堆栈现在[1]
• 现在你回到了1,你已经完成了左边,所以右转到3,推它,堆栈现在[1 3]
• 向左走,堆叠现在[1 3 6]
• 6是叶子,不是你要找的东西,所以pop,stack是[1 3]
• 现在你必须从3向右走,推它,现在堆栈[1 3 7]
• 可是等等!看!您已到达所需的节点!看看你的筹码!这是你想要的道路.

Answer 2

您将获得一个二叉树(根节点)..并且会给出一个键,该键可能在树中,也可能不在树中.您必须找到从根到节点的完整路径.

例:

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

你给了节点Z(或节点的密钥)和给定的节点A(根)所以你的输出应该是

ABDKZ

如果给出M,则输出应为ACEM

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 + " ";
    }
}

}