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

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

有没有人知道我如何实现这一点?任何输入将不胜感激,我真诚地感谢新手编码器。


波斯汪
浏览 216回答 2
2回答

慕粉2291655

完美解决/**  * @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           }         }         //继续循环       }     },

LEATH

为了找到从一个节点到另一个节点的路径,您必须从原始节点递归遍历树,直到它的子节点、它们的子节点等等,直到到达目标节点。到达目标节点后,您需要将带您到达目标节点的节点路径回溯到根节点。一种方法是修改版本的前序遍历 ,首先检查根,然后是左子树,然后是右子树。public boolean getPath(root, value){&nbsp; &nbsp; if(root == null){&nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; }&nbsp; &nbsp; if(root.value === value){&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(root.value);&nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; }&nbsp; &nbsp; int onPath = getPath(root.left, value);&nbsp; &nbsp; if(onPath){&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(root.value);&nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; }&nbsp; &nbsp; onPath = getPath(root.right,value);&nbsp; &nbsp; if(onPath){&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(root.value);&nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; }&nbsp; &nbsp; return false; //a path was never found}&nbsp;在上面的方法中,我们将 的值root与目的地进行比较value。如果它们不相等,我们检查左子树。如果目标不在左子树中,则检查右子树。如果仍然没有找到目的地,false则返回,以便在返回递归调用堆栈时,我们可以让节点的父节点知道没有从该节点到目的地的路径。但是,如果找到了目的地,那么我们返回,true以便在返回递归调用堆栈时,我们可以告诉节点的父节点和它的父节点,等等,找到了一条路径。
打开App,查看更多内容
随时随地看视频慕课网APP

相关分类

Java