思路

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

解法

  1. class Solution {
  2.     public List<Integer> postorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<Integer>();
  4.         postorder(root, res);
  5.         return res;
  6.     }
  8.     public void postorder(TreeNode root, List<Integer> res){
  9.         if(root == null){
  10.             return;
  11.         }
  12.         postorder(root.left, res);
  13.         postorder(root.right, res);
  14.         res.add(root.val);
  15.     }
  16. }
  • 时间复杂度：leetcode-145：二叉树的后序遍历 - 图1，其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次
  • 空间复杂度：leetcode-145：二叉树的后序遍历 - 图2，为递归过程中栈的开销，平均情况下为leetcode-145：二叉树的后序遍历 - 图3，最坏情况下树呈现链状，为 leetcode-145：二叉树的后序遍历 - 图4