树的后序遍历的两种实现

今天介绍一下树的后序遍历

什么是后序遍历

  所谓遍历就是将集合中的所有元素都访问一遍，由于树是一种非线性结构，所以它的遍历方式有很多种：

• 前序遍历 ：根左右
• 中序遍历 ：左根右
• 后序遍历 ：左右根
• 按层遍历 ：逐层访问

  接下来我们用动图的方式，看一下树的后序遍历过程：

递归

  我们将动图翻译成代码，就得到了递归的实现方法
  定义树

1class TreeNode{
2    public TreeNode left;
3    public TreeNode right;
4    public int val;
5
6    public TreeNode(int val){
7        this.val = val;
8    }
9}

  方法实现

1 private static void function(TreeNode head){
2        if(head == null){
3            return;
4        }
5        function(head.left);
6        function(head.right);
7        System.out.println(head.val);
8    }

  可以看到递归的方法非常的简单，甚至看一遍就可以记住了，通常这道题到这为止就算做完了，但是你真的理解这段代码吗？或者说如果不用递归，你可以用循环的方式实现这道题吗？

循环

  任何用递归做的题，我们用循环的方式都可以解决。解决的思路大体相同，用代码实现递归的调用栈，我们依然要对照着图示来看，首先我们将树的所有左节点入栈，然后出栈，去遍历它的右节点，将右节点入栈，以此重复上述的过程。具体代码如下(推荐使用方法二，可大概看一下，直接去看方法二)：

 1    private static void function(TreeNode head) {
 2        if (head == null) {
 3            return;
 4        }
 5        Stack<TreeNode> stack = new Stack<>();
 6        Stack<TreeNode> repeatStack = new Stack<>();
 7        TreeNode cur = head;
 8        pushLeftNode(stack, cur);
 9        while (!stack.empty()) {
10            cur = stack.peek();
11            if (!repeatStack.empty() && repeatStack.peek() == cur) {
12                repeatStack.pop();
13                stack.pop();
14                System.out.println(cur.val);
15            } else {
16                if (cur.right != null) {
17                    repeatStack.push(cur);
18                    pushLeftNode(stack, cur.right);
19                } else {
20                    cur = stack.pop();
21                    System.out.println(cur.val);
22                }
23            }
24        }
25    }
26
27    private static void pushLeftNode(Stack<TreeNode> stack, TreeNode node) {
28        stack.push(node);
29        while (node.left != null) {
30            stack.push(node.left);
31            node = node.left;
32        }
33    }

  这种做法比较符合直觉，我们模拟出了一个调用栈，然后借助另一个repeatStack，用来过滤遍历过的元素，防止元素重复遍历的过程。

  还有其他的循环方法，我们可以对方法一的stack进行拆分，拆分出的2个栈，一个用来存储结果，一个用来计算。

 

 1private static void function(TreeNode head) {
 2        if (head == null) {
 3            return;
 4        }
 5        Stack<TreeNode> stack1 = new Stack<>();
 6        Stack<TreeNode> stack2 = new Stack<>();
 7        stack1.push(head);
 8        while (!stack1.empty()) {
 9            TreeNode cur = stack1.pop();
10            stack2.push(cur);
11            if(cur.left != null){
12                stack1.push(cur.left);
13            }
14            if(cur.right != null){
15                stack1.push(cur.right);
16            }
17        }
18
19        while(!stack2.empty()){
20            System.out.println(stack2.pop().val);
21        }
22    }