二叉树后序遍历（递归、迭代）

题目链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

给定一个二叉树的根节点 root ，返回 它的 后序 遍历 。 代码如下：

1.递归法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
          
   
    public List<Integer> postorderTraversal(TreeNode root) {
          
   
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }

    public void postorder(TreeNode root, List<Integer> res) {
          
   
        if (root == null) {
          
   
            return;
        }
        postorder(root.left, res);//左
        postorder(root.right, res);//右
        res.add(root.val);//根
    }
}

2.迭代法

解题思路： 与中序的不同之处在于：中序遍历中，从栈中弹出的节点，其左子树是访问完了，可以直接访问该节点，然后接下来访问右子树。

后序遍历中，从栈中弹出的节点，我们只能确定其左子树肯定访问完了，但是无法确定右子树是否访问过。 因此，我们在后序遍历中，引入了一个prev来记录历史访问记录。

当访问完一棵子树的时候，我们用prev指向该节点。 这样，在回溯到父节点的时候，我们可以依据prev是指向左子节点，还是右子节点，来判断父节点的访问情况。

class Solution {
          
   
    public List<Integer> postorderTraversal(TreeNode root) {
          
   
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
          
   
            return res;
        }

        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
          
   
            while (root != null) {
          
   
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
          
   
                res.add(root.val);
                prev = root;
                root = null;
            } else {
          
   
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
}