友情支持

如果您觉得这个笔记对您有所帮助，看在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
0145 12
0145 13
0145 14
0145 15
0145 16
0145 17
0145 18
0145 19
0145 20
0145 21
0145 22
0145 23
0145 24
0145 25
0145 26
0145 27
0145 28
0145 29
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 缓存 →