java实现二叉树的后序遍历

标题：java实现二叉树的后序遍历

/** * 我的二叉树 【后序遍历】 * @author dell * */ public class TestMyTreeB03 { /** * 测试遍历二叉树的后序遍历【先输出节点的值】 * @param p */ public void backorder(IntNode p) { if(p == null) { return ; }else { this.backorder(p.left); this.backorder(p.right); System.out.print(p.val + " "); } } /** * 执行用时：1 ms, 在所有 Java 提交中击败了51.35% 的用户 内存消耗：36.5 MB, 在所有 Java 提交中击败了99.81% 的用户 * @param p */ public void backorder02(IntNode p) { Deque<IntNode> s = new LinkedList<>(); if(p == null) { return ; } s.push(p); while(!s.isEmpty()) { while(s.peek().left != null) { //一直遍历左边 IntNode node = s.peek().left; s.push(node); } IntNode node = s.peek().right; //取右节点 while(!s.isEmpty() && node == null) { System.out.print(s.peek().val + " "); IntNode m = s.pop(); if(s.isEmpty()) { break; } node = s.peek().right; while(node == m) { //右支路 回退 m = s.pop(); System.out.print(m.val + " "); if(s.isEmpty()) { break; } node = s.peek().right; } } if(!s.isEmpty() && node != null) { //若没有!s.isEmpty() f d g h e b i k j c a i k j c k j k s.push(node); } } } @Test public void test02() { IntNode p1 = new IntNode('a'); IntNode p2 = new IntNode('b'); IntNode p3 = new IntNode('c'); IntNode p4 = new IntNode('d'); IntNode p5 = new IntNode('e'); IntNode p6 = new IntNode('f'); IntNode p7 = new IntNode('g'); IntNode p8 = new IntNode('h'); IntNode p9 = new IntNode('i'); IntNode p10 = new IntNode('j'); IntNode p11 = new IntNode('k'); p1.left = p2; p1.right = p3; p2.left = p4; p2.right = p5; p4.right = p6; p5.left = p7; p5.right = p8; p3.left = p9; p3.right = p10; p10.right =p11; System.out.println("使用递归的后序遍历"); this.backorder(p1); System.out.println(); System.out.println("不使用递归的后序遍历"); this.backorder02(p1); System.out.println(); } }