LeetCode算法系列 145. 二叉树的后序遍历

LeetCode算法系列（Java版） 144. 二叉树的前序遍历
LeetCode算法系列（Java版） 94. 二叉树的中序遍历
LeetCode算法系列（Java版） 145. 二叉树的后序遍历

力扣原题

145. 二叉树的后序遍历

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

示例:

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

输出: [3,2,1]

二叉树

二叉树是一种「数据结构」，简单来说，就是一个包含节点，以及它的左右孩子的一种数据结构。

遍历方式

如果对每一个节点进行编号，你会用什么方式去遍历每个节点呢？

1. 前序遍历

如果你按照 根节点 -> 左孩子 -> 右孩子 的方式遍历，即「先序遍历」，每次先遍历根节点，遍历结果为 1 2 4 5 3 6 7；

2. 中序遍历

如果你按照 左孩子 -> 根节点 -> 右孩子 的方式遍历，即「中序遍历」，遍历结果为 4 2 5 1 6 3 7；

3. 后序遍历

如果你按照 左孩子 -> 右孩子 -> 根节点 的方式遍历，即「后序遍历」，遍历结果为 4 5 2 6 7 3 1；

4. 层次遍历

「层次遍历」就是按照每一层从左向右的方式进行遍历，遍历结果为 1 2 3 4 5 6 7。

方法一：递归

思路与算法

二叉树的后序遍历：按照访问 左子树——右子树——根节点 的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

定义 postorder(root) 表示当前遍历到 root 节点的答案。按照定义，我们只要递归调用 postorder(root->left) 来遍历 root 节点的左子树，然后递归调用 postorder(root->right) 来遍历 root 节点的右子树，最后将 root 节点的值加入答案即可，递归终止的条件为碰到空节点。

代码实现

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);
    }
}

复杂度分析

时间复杂度：，其中是二叉树的节点数。每一个节点恰好被遍历一次。
空间复杂度：，为递归过程中栈的开销，平均情况下为，最坏情况下树呈现链状，为。

方法二：迭代

思路与算法

前序遍历的过程是中左右。
将其转化成 中右左。也就是压栈的过程中优先压入左子树，在压入右子树。
然后将这个结果返回来，这里是利用栈的先进后出倒序打印（左右中）。

代码实现

public static void postOrderIteration(TreeNode head) {
  if (head == null) {
   return;
  }
  Stack<TreeNode> stack1 = new Stack<>();
  Stack<TreeNode> stack2 = new Stack<>();
  stack1.push(head);
  while (!stack1.isEmpty()) {
   TreeNode node = stack1.pop();
   stack2.push(node);
   if (node.left != null) {
    stack1.push(node.left);
   }
   if (node.right != null) {
    stack1.push(node.right);
   }
  }
  while (!stack2.isEmpty()) {
   System.out.print(stack2.pop().value + " ");
  }
 }