LeetCode: 145. Binary Tree Postorder Traversal

友情支持

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

支付宝

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

wx jikerizhi

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

145. Binary Tree Postorder Traversal

LeetCode - Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively?

解题分析

这个题有些麻烦。

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

还可以使用两个 Stack。

甚至一个 Stack。

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

迭代实现

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

核心思想为：

每拿到一个节点就把它保存在栈中
继续对这个节点的 左子树 重复 过程1，直到左子树为空
因为保存在栈中的节点都遍历了 左子树 但是没有遍历 右子树，所以对栈中节点出栈并对它的 右子树 重复 过程1
直到遍历完所有节点

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

思考题

如何使用一个栈来解决这个问题？
对比一下前根遍历和后跟遍历的区别。参考： 145. 二叉树的后序遍历。