后序遍历

给定一个二叉树的根节点 root ，返回它的 后序 遍历。
后序遍历：按照访问右子树——左子树——根节点的方式遍历这棵树

示例

[二叉树] 系列：非递归后序遍历 - 图1

方法一：递归

  1. class Solution {
  2.     List<Integer> res = new ArrayList<>();
  3.     public List<Integer> postorderTraversal(TreeNode root) {
  4.         if(root == null) return res;
  5.         postorderTraversal(root.left);
  6.         postorderTraversal(root.right);
  7.         res.add(root.val);
  8.         return res;
  9.     }
  10. }

方法二：迭代

1.初始化返回列表，判空，初始化栈，初始化prev，cur两个节点
2.循环：当前节点不空或者栈不空

  • 从当前节点开始一直往左分别入栈
  • 出栈，判断

1.当前节点右孩子为空或者右孩子是前驱节点（父节点出栈之后右孩子不空但是都已经添加到结果列表），将节点值添加到返回列表，更新prev为当前节点，cur为空。
2.当前节点右孩子不为空：当前节点再次入栈，当前节点指向右孩子。
3.返回res

  1. class Solution {
  2.     public List<Integer> postorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<>();
  4.         if(root == null) return res;
  5.         LinkedList<TreeNode> stack = new LinkedList<>();
  6.         TreeNode cur = root;
  7.         TreeNode prev = null;
  8.         while(cur != null || !stack.isEmpty()){
  9.             while(cur != null){
  10.                 stack.addFirst(cur);
  11.                 cur = cur.left;
  12.             }
  13.             cur = stack.removeFirst();
  14.             if(cur.right == null || cur.right == prev){
  15.                 res.add(cur.val);
  16.                 prev = cur;
  17.                 cur = null;
  18.             }else{
  19.                 stack.addFirst(cur);
  20.                 cur = cur.right;
  21.             }
  22.         }
  23.         return res;
  24.     }
  25. }

方法三：Morris中序遍历

能将非递归的中序遍历空间复杂度降为 O(1)。