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

Question

一段时间以来，我一直试图解决这个问题，但我并没有真正解决它。本质上，给定一些二叉树和该树上的一个节点，您将如何找到从该给定节点返回到根节点的路径？有没有人知道我如何实现这一点？任何输入将不胜感激，我真诚地感谢新手编码器。

Answer 1

完美解决

/**
 * @param tree 树
 * @param nodekey 指定节点的key
 * @return 路劲数组
 */
get路劲(tree,nodekey){
      let keys=[]
      if(!tree||!nodekey){
        return keys
      }
      //遍历树节点
      for (let index = 0; index < tree.length; index++) {
        let e = tree[index];
        //找到这个就停止了
        if(e.key===nodekey){
          keys.push(e.key)
          return keys
        }else if(e.children&&e.children.length>0){
          let keys2=this.get路劲(e.children,nodekey)
          //如果key2数组不为空则说明从当前节点的子节点找到了该节点
          if(keys2&&keys2.length>0){
            keys2.push(e.key)//将当前节点添加到路劲中
            return keys2
          }
        }
        //继续循环
      }
    },

Answer 2

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

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则返回，以便在返回递归调用堆栈时，我们可以让节点的父节点知道没有从该节点到目的地的路径。但是，如果找到了目的地，那么我们返回，true以便在返回递归调用堆栈时，我们可以告诉节点的父节点和它的父节点，等等，找到了一条路径。