LeetCode-94.二叉树的中序遍历

发表于 分类于

题目描述

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

1
2
输入：root = [1,null,2,3]
输出：[1,3,2]
1
2
输入：root = []
输出：[]
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 inorderTravelsal(_ root: TreeNode?) -> [Int] {
  guard let root = root else {
    return []
  }
  var result = [Int]()

  let leftList = inorderTravelsal(root.left)
  let rightList = inorderTravelsal(root.right)
  result.append(contentsOf: leftList)
  result.append(root.val)
  result.append(contentsOf: rightList)
  
  return result
}

遍历法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func inorderTraversal(_ root: TreeNode?) -> [Int] {
  var res = [Int]()
  var stack = [TreeNode]()
  
  var cur = root
  while cur !== nil || !stack.isEmpty {
    // 遍历当前节点的左子树，并入栈遍历到的节点，直到左节点为空
    while cur !== nil {
      stack.append(cur!)
      cur = cur?.left
    }
    // 取出栈顶节点，输出该节点，并遍历该节点的右子树
    cur = stack.popLast()
    res.append(cur!.val)
    cur = cur?.right
  }
  
  return res
}