友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

微信

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

145. 二叉树的后序遍历

LeetCode - 145. 二叉树的后序遍历

给你一棵二叉树的根节点 root，返回其节点值的 后序遍历。

示例 1：

输入：root = [1,null,2,3]

输出：[3,2,1]

解释：

0145 01

示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[4,6,7,5,2,9,8,3,1]

解释：

0145 02

示例 3：

输入：root = []

输出：[]

示例 4：

输入：root = [1]

输出：[1]

提示：

  • 树中节点的数目在范围 [0, 100] 内

  • -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

思路分析

这个题有些麻烦。

我的解法是使用 Stack 和 Set（保存处理过子节点，直接弹出，不再处理）。

还可以使用两个 Stack。

甚至一个 Stack。

迭代实现

下面终点讲解一下迭代实现。

核心思想为：

  1. 每拿到一个 节点 就把它保存在 栈 中

  2. 继续对这个节点的 左子树 重复 过程1，直到左子树为 空

  3. 因为保存在 栈 中的节点都遍历了 左子树 但是没有遍历 右子树，所以对栈中节点 出栈 并对它的 右子树 重复 过程1

  4. 直到遍历完所有节点

0145 11
TODO：还需要加强迭代遍历的实现！

  • 一刷

  • 二刷(递归)

  • 二刷(栈)

  • 三刷(栈)

  • 四刷(Morris)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

public List<Integer> postorderTraversal(TreeNode head) {
  if (Objects.isNull(head)) {
    return Collections.emptyList();
  }
  List<Integer> result = new LinkedList<>();
  Stack<TreeNode> s1 = new Stack<>();
  Stack<TreeNode> s2 = new Stack<>();
  s1.push(head);
  TreeNode c = null;
  while (!s1.empty()) {
    head = s1.pop();
    s2.push(head);
    if (Objects.nonNull(head.left)) {
      s1.push(head.left);
    }
    if (Objects.nonNull(head.right)) {
      s1.push(head.right);
    }
  }
  while (!s2.empty()) {
    result.add(s2.pop().val);
  }
  return result;
}

public List<Integer> postorderTraversal1(TreeNode root) {
  if (Objects.isNull(root)) {
    return Collections.emptyList();
  }
  List<Integer> result = new LinkedList<>();
  Stack<TreeNode> stack = new Stack<>();
  stack.push(root);
  Set<TreeNode> deal = new HashSet<>();
  while (!stack.empty()) {
    boolean updated = false;
    TreeNode node = stack.peek();
    if (!deal.contains(node)) {
      if (Objects.nonNull(node.right)) {
        stack.push(node.right);
        updated = true;
      }
      if (Objects.nonNull(node.left)) {
        stack.push(node.left);
        updated = true;
      }
      deal.add(node);
      if (updated) {
        continue;
      }
    }
    node = stack.pop();
    result.add(node.val);
  }
  return result;

}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-06-16 11:24
 */
public List<Integer> postorderTraversal(TreeNode head) {
  List<Integer> result = new ArrayList<>();
  postorderTraversal(head, result);
  return result;
}

private void postorderTraversal(TreeNode head, List<Integer> result) {
  if (head == null) {
    return;
  }
  postorderTraversal(head.left, result);
  postorderTraversal(head.right, result);
  result.add(head.val);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public List<Integer> postorderTraversal(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  Deque<TreeNode> stack = new LinkedList<>();
  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) {
      result.add(root.val);
      prev = root;
      root = null;
    } else {
      stack.push(root);
      root = root.right;
    }
  }
  return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2026-09-07 07:48:14
 */
public List<Integer> postorderTraversal(TreeNode root) {
  if (null == root) {
    return Collections.emptyList();
  }
  List<Integer> result = new ArrayList<>();
  Deque<TreeNode> stack = new ArrayDeque<>();
  stack.push(root);
  while (!stack.isEmpty()) {
    TreeNode peek = stack.peek();
    if (peek.left == null && peek.right == null) {
      stack.pop();
      result.add(peek.val);
    } else if (peek.left != null) {
      TreeNode left = peek.left;
      peek.left = null;
      stack.push(left);
    }else {
      TreeNode right = peek.right;
      peek.right = null;
      stack.push(right);
    }
  }
  return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-06-16 11:24
 */
public List<Integer> postorderTraversal(TreeNode head) {
  List<Integer> result = new ArrayList<>();
  TreeNode curr = head, mostRight = null;
  while (curr != null) {
    mostRight = curr.left;
    if (mostRight != null) {
      while (mostRight.right != null && mostRight.right != curr) {
        mostRight = mostRight.right;
      }
      if (mostRight.right == null) {
        mostRight.right = curr;
        curr = curr.left;
        continue;
      } else {
        mostRight.right = null;
        result.addAll(getEdge(curr.left));
      }
    }
    curr = curr.right;
  }
  result.addAll(getEdge(head));
  return result;
}

private List<Integer> getEdge(TreeNode head) {
  TreeNode tail = reverseEdge(head);
  TreeNode curr = tail;
  List<Integer> result = new ArrayList<>();
  while (curr != null) {
    result.add(curr.val);
    curr = curr.right;
  }
  return result;
}

private TreeNode reverseEdge(TreeNode head) {
  TreeNode prev = null;
  TreeNode curr = head;
  while (curr != null) {
    TreeNode next = curr.right;
    curr.right = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

思考题

  1. 如何使用一个栈来解决这个问题？ 答：利用树中的指针作为标记符号来区分处理栈顶元素：如果没有子树，则出栈；如果有左子树，则将左子树加入栈；如果没有左子树，有右子树，则将右子树加入栈。

  2. 对比一下前根遍历和后跟遍历的区别。 参考： 145. 二叉树的后序遍历。

参考资料

  1. 145. 二叉树的后序遍历 - 帮你对二叉树不再迷茫，彻底吃透前中后序递归法（递归三部曲）和迭代法…​

  2. 145. 二叉树的后序遍历 - 官方题解

  3. 145. 二叉树的后序遍历 - 迭代解法，时间复杂度 O(n)，空间复杂度 O(n)

← Previous: 144. 二叉树的前序遍历 | ↑ Up: LeetCode 解题笔记 | Next: 146. LRU 缓存 →