145. 二叉树的后序遍历

145. 二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

代码实现

• 迭代实现

 public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        if (root == null) return linkedList;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode lastPopNode = root;
        while (!stack.isEmpty()){
            TreeNode topNode = stack.peek();
            if ((topNode.left == null && topNode.right == null) || (topNode.left == lastPopNode || topNode.right == lastPopNode)) {
                lastPopNode =  stack.pop();
                linkedList.add(lastPopNode.val);
            }else {
                if (topNode.right != null){
                    stack.push(topNode.right);
                }
                if (topNode.left != null){
                    stack.push(topNode.left);
                }
            }
        }
        return linkedList;
    }

• 递归实现

LinkedList<Integer> linkedList = new LinkedList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return linkedList;
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        linkedList.add(root.val);
        return linkedList;
    }

解题思路

• 迭代实现
  利用栈实现

1. 将root入栈
2. 循环执行以下操作直到栈为空
   2.1. 如果栈顶是叶子节点或者上一次访问的节点是栈顶节点的子节点，弹出栈顶节点进行访问
   2.2. 否则，将栈顶节点的右左子节点按顺序入栈

• 递归实现

1. 后序遍历左子树
2. 后序遍历右子树
3. 访问根节点