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

发表于 分类于

题目描述

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

示例1

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

示例2

1
2
输入：root = []
输出：[]

示例3

1
2
输入：root = [1]
输出：[1]

提示：

  • 树中节点的数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

题解

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func postorderTraversal(_ root: TreeNode?) -> [Int] {
  guard let root = root else {
    return []
  }
  var result = [Int]()

  let leftList = postorderTraversal(root.left)
  let rightList = postorderTraversal(root.right)
  result.append(contentsOf: leftList)
  result.append(contentsOf: rightList)
  result.append(root.val)

  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
func postorderTraversal2(_ root: TreeNode?) -> [Int] {
  var result = [Int]()
  var stack = [TreeNode]()
  var cur = root
  var flag: TreeNode? = nil

  while cur != nil || !stack.isEmpty {
      while cur != nil {
          stack.append(cur!)
          cur = cur?.left
      }

      cur = stack.removeLast()
      if cur?.right === nil || cur?.right === flag {
          result.append(cur!.val)
          flag = cur
          cur = nil
      } else {
          stack.append(cur!)
          //右子树不为空，即上面出栈后又继续入栈，在更新cur值，再去从头循环
          cur = cur?.right
      }
  }

  return result
}

遍历2: 左右子树均入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func postorderTraversal3(_ root: TreeNode?) -> [Int] {
  guard let root = root else { return [] }
  
  var result = [Int]()
  var stack = [root]
  
  while !stack.isEmpty {
    let cur = stack.removeLast()
    result.insert(cur.val, at: 0) // 逆序添加到结果数组中
    // 先添加左子树，后添加右子树，这样取出的时候就是先取出右子树，逆序添加到结果数组中时就是左-右-中
    if let left = cur.left {
      stack.append(left)
    }
    if let right = cur.right {
      stack.append(right)
    }
  }
  return result
}