1.非递归后序遍历二叉树
- Java code
// 后序遍历非递归 public static void PostOrder2(BinTree t) { Stack<BinTree> s = new Stack<BinTree>(); Stack<Integer> s2 = new Stack<Integer>(); Integer i = new Integer(1); while (t != null || !s.empty()) { while (t != null) { s.push(t); s2.push(new Integer(0)); t = t.lchild; } while (!s.empty() && s2.peek().equals(i)) { s2.pop(); System.out.print(s.pop().date); } if (!s.empty()) { s2.pop(); s2.push(new Integer(1)); t = s.peek(); t = t.rchild; } } } 前序中序非递归我都能理解 后续中多加了一个标志栈
不是很清楚这个算法的具体过程 求详细解释
2.求二叉树中最长的路径
意思就是根节点到某个叶子节点的路径最长 输出这个路径
3.求某个节点(值等于value的节点)的深度(层次数)
最好能告诉我具体的算法思路
------解决方案--------------------
2,3用递归可以么
2，返回每棵子树的最长路径，将左右对比取大的那个
3，每递进一层就把计数加一
------解决方案--------------------
第2、3，都可以采用二叉树遍历完成，用深度优先遍历。
第一题嘛……简单说，就是为了表示该节点的右子树是否全部遍历完毕。如果没有，则为0，如果已遍历完，则置1，然后才输出这个节点的值。这就是后序遍历的意思。
------解决方案--------------------
Stack<Integer> s2 是个标志位
=0 表示S里 （s = Stack<BinTree>）压了一个bintree， 当前要打印的是 左子树
=1 表示S里压的是一个bintree, 当前 左子树已经打印了，所以现在应该打印 中节点 然后遍历右子树