时间戳

首页 > 解决方案 > 二叉树中从给定节点到根的路径

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

问题描述

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

有谁知道我如何实现这一点？任何输入将不胜感激，我衷心感谢新手编码器。

标签： javarecursionbinary-tree

解决方案

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

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与 destination的值进行比较value。如果它们不相等，我们检查左子树。如果目的地不在左子树中，则检查右子树。如果仍未找到目的地，false则返回，以便在返回递归调用堆栈时，我们可以让节点的父节点知道从该节点到目的地没有路径。但是，如果找到了目的地，那么我们返回true，以便在返回递归调用堆栈时，我们可以告诉节点的父节点及其父节点等等，已经找到了一条路径。

推荐阅读