政府查询网站建设方案/百度网站安全检测

问题：对于一棵二叉树，输出所有从根结点到叶子结点的路径。

主要思路是和二叉树的非递归式后序遍历差不多，都是先用一个栈来存储已经访问过的结点，直至遍历完它自己、它的左子树、它的右子树。但是后序遍历和其它两种遍历方式还是有些不同，前序遍历的过程是：结点入栈-->访问结点-->访问左子树-->返回结点-->结点出栈-->访问右子树；中序遍历的过程是：结点入栈-->访问左子树-->返回结点-->访问结点-->结点出栈-->访问右子树；而后序遍历的过程是：结点入栈-->访问左子树-->返回结点-->访问右子树-->返回结点-->访问结点-->结点出栈。可以看到，后序遍历有再次返回了结点，这就带来一个问题，怎么判断某次返回结点到底是从左子树返回的？还是从右子树返回的？

解决后序遍历的这个问题的方法是：当从栈中弹出一个元素时，检查这个元素与栈顶元素的右子结点是否相同，如果相同说明是从右子树返回，此时已经完成了左右子树的遍历，下一步只需再弹出元素并访问该结点即可。

说了半天后序遍历，其实在输出路径的问题上我们采用的是前序遍历方式，先访问一个结点，然后是左子树，然后才是右子树，毕竟这样才比较自然一点。只是在写代码的过程中遇到了一个问题，也需要判断栈中的某个结点是否已经访问过它的左右子树，此时采用了和判断后序遍历是从哪个子树返回一样的解决方案。

代码如下：

import java.util.Stack;public class PathFromRootToLeaf {static class Node<T> {T t;Node left;Node right;@Overridepublic String toString() {return t.toString();}}public static void printPathStack(Stack stack) {for (int i = 0; i < stack.size(); i++) {System.out.print(stack.elementAt(i) + " ");}System.out.println();}//可以看到和前序遍历的过程差不多public static void printPath(Node node) {if (node == null) return;Stack<Node> path = new Stack<>();end:while (true) {//将左结点入栈，直至没有左子树while (node != null) {path.push(node);node = node.left;}if (path.isEmpty()) break;//访问栈顶的结点，如果是叶子结点则输出路径，否则访问其右结点node = path.peek();//如果是叶子结点if (isLeaf(node)) {printPathStack(path);path.pop();  //弹出nodeNode parent = path.peek();  //由于栈中存储的是路径，所以path.peek()一定是node的父结点//如果node是parent的右子树，说明parent左子树已经遍历过，那么需要继续弹出parent结点。//如果parent没有右子树，同样地需要弹出parent结点，因为parent的所有子树已经遍历过。//这个过程需要重复进行，找出路径中一个结点，它的右子树需要遍历。while (parent.right == node || parent.right == null) {node = path.pop();//如果栈为空，说明根结点的右子树也已经遍历完成，那么直接退出循环if (!path.isEmpty()) {parent = path.peek();} else {break end;}}//找到一个parent的右子树没有遍历过node = parent;}//访问node的右子树node = node.right;}}private static boolean isLeaf(Node node) {return node.right == null && node.left == null;}public static void preOrder(Node root) {if (root == null) return;Stack<Node> stack = new Stack<>();while (true) {while (root != null) {System.out.println(root);stack.push(root);root = root.left;}if (stack.isEmpty()) break;root = stack.pop();root = root.right;}}public static void main(String[] args) {Node<Integer> root = new Node<>();Node<Integer> a = new Node<>();Node<Integer> b = new Node<>();Node<Integer> c = new Node<>();Node<Integer> d = new Node<>();Node<Integer> e = new Node<>();Node<Integer> f = new Node<>();Node<Integer> g = new Node<>();Node<Integer> h = new Node<>();root.t = 1;a.t = 2;b.t = 3;c.t = 4;d.t = 5;e.t = 6;f.t = 7;g.t = 8;h.t = 9;root.left = a;root.right = b;a.left = c;a.right = d;c.right = e;e.left = f;e.right = g;d.right = h;printPath(root);}
}