树的后序遍历的两种实现

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

什么是后序遍历

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

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

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

递归

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

class TreeNode{
    public TreeNode left;
    public TreeNode right;
    public int val;

    public TreeNode(int val){
        this.val = val;
    }
}

  方法实现

 private static void function(TreeNode head){
        if(head == null){
            return;
        }
        function(head.left);
        function(head.right);
        System.out.println(head.val);
    }

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

循环

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

    private static void function(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> repeatStack = new Stack<>();
        TreeNode cur = head;
        pushLeftNode(stack, cur);
        while (!stack.empty()) {
            cur = stack.peek();
            if (!repeatStack.empty() && repeatStack.peek() == cur) {
                repeatStack.pop();
                stack.pop();
                System.out.println(cur.val);
            } else {
                if (cur.right != null) {
                    repeatStack.push(cur);
                    pushLeftNode(stack, cur.right);
                } else {
                    cur = stack.pop();
                    System.out.println(cur.val);
                }
            }
        }
    }

    private static void pushLeftNode(Stack<TreeNode> stack, TreeNode node) {
        stack.push(node);
        while (node.left != null) {
            stack.push(node.left);
            node = node.left;
        }
    }

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

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

private static void function(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(head);
        while (!stack1.empty()) {
            TreeNode cur = stack1.pop();
            stack2.push(cur);
            if(cur.left != null){
                stack1.push(cur.left);
            }
            if(cur.right != null){
                stack1.push(cur.right);
            }
        }

        while(!stack2.empty()){
            System.out.println(stack2.pop().val);
        }
    }