寻找二叉树上从根节点到给定节点的路径一、递归思想:利用堆栈结构存储路径上的节点，首先从根节点开始一直向左寻找，向左找到后返回true； 否则，如果找不到左边，右边的子树不是空的，就继续寻找右边的子树。 如果找不到左右子树，则弹出堆栈的顶级节点并返回false。 方法执行完成后，保存在堆栈中的元素将成为从根到指定节点的路径。
publicstaticbooleansearchnode (treenode root，StackTreeNode s，TreeNode node ) { if } root==null ) return false； s.push(root )； if(root.val==node.val ) return true； 布尔b=假； //先去左子树看看if(root.left！=null ) b=searchnode(root.left，s，node )； //找不到左边的子树，右边的子树不空着的情况下，才if (！ b root.right！=null ) b=searchnode(root.right，s，node )； //左右都找不到，弹出堆栈顶部要素if (！ b ) s.pop )； 返回b； }程序运行结束后，堆栈中将保存请求的路径。 参数root表示根节点，s表示堆栈，node表示给定的节点。 如果不想用值进行比较，可以将if(root.val==node.val )直接替换为if ) root==node )，道理也是一样的。
二、非递归实现思想：这有点复杂，当然要借栈完成。 其实这里与二叉树的非递归超前扫描的思想相似，但在此基础上进行了一些改造。 首先，创建新堆栈并保存根节点。 然后一直向左找，在找的时候把节点放到堆栈里。 在向左寻找的过程中遇到给定的节点，输出并返回的过程很容易理解。 关键是弹下一个堆栈的过程。 如果在向左查找时遇到null，则表示当前堆栈顶部元素的左子树为null。 那么，开始寻找堆栈最上面元素右边部分的树。 将p作为栈顶元素，栈顶元素的右部分树为null时，弹出栈顶元素，用pre保存刚弹出的元素。 设定pre是因为，在当前栈顶元素的右部分树不为null的情况下，不容易弹出，所以必须先去寻找右部分树。 这是因为，在右部分树被弹出的情况下，如果右部分树中一定没有，则可以弹出当前的节点。
publicstaticvoidsearchnode (treenode root，treenode ) if ) root==null||node==null ) return； StackTreeNode s=new Stack (； TreeNode p=root； TreeNode pre=null； //上次堆栈的节点While(P！=空| |！ s.isEmpty () (while ) ) p！=null(//这个while循环的思想还是一直向左找，找的过程节点进入堆栈，找到后打印回来。 s.push(p； if(p.val==node.val ) treenode treenode : s (system.out.print ) treenode.val ' )； } return； (} p=p.left； //至此，表示堆栈顶部元素左部分的树为null，开始寻找堆栈顶部元素右部分的树。 if (！ s.isEmpty () ) { p=s.peek； //如果堆栈顶部元素的右部分树为空或遍历右部分树，则弹出堆栈。 while(p.right==null||pre！=nullp.right==pre({pre=s.pop )； p=s.peek (； (//p的右部分树p=p.right； } }
posted @ 2018-08-161:23 neu _ swdsj阅读(…)注释…)编辑收藏