二叉树中从给定节点到根的路径

Question

我已经尝试解决这个问题一段时间了，但我并没有真正解决这个问题。本质上，给定一些二叉树和该树上的一个节点，您将如何找到从该给定节点返回到根的路径？

有人知道我该如何实现吗？任何输入将不胜感激，我衷心感谢新手编码员。

Answer 1

为了找到从一个节点到另一个节点的路径，您必须递归地从源节点向下遍历树到它的子节点，它们的子节点等等，直到到达目标节点。到达目标节点后，您需要将将您带到该目标节点的节点路径回溯到根。一种方法是 预序遍历 的修改版本，其中首先检查根，然后是它的左子树，然后是它的右子树。

public boolean getPath(root, value){
    if(root == null){
        return false;
    }
    if(root.value === value){
        System.out.println(root.value);
        return true;
    }
    int onPath = getPath(root.left, value);
    if(onPath){
        System.out.println(root.value);
        return true;
    }
    onPath = getPath(root.right,value);
    if(onPath){
        System.out.println(root.value);
        return true;
    }
    return false; //a path was never found
}

在上面的方法中，我们将 root 的值与目标 value 进行比较。如果它们不相等，我们检查左子树。如果目的地不在左子树中，则检查右子树。如果仍未找到目的地，则 false 被 returned 以便在返回递归调用堆栈时，我们可以让节点的父节点知道没有从该节点到目的地的路径。但是，如果找到了目的地，那么我们 return true 以便在返回递归调用堆栈时，我们可以告诉节点的父节点及其父节点等已找到路径。

二叉树中从给定节点到根的路径

Path from given node to root in a binary tree

java

recursion

binary-tree