LeetCode-144.二叉树的前序遍历

发表于 分类于

题目描述

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例1

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

示例2

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

示例3

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

提示：

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

题解

1
2
3
4
5
6
7
8
9
10
11
12
/** 二叉树节点 */
class TreeNode {
  var val: Int
  var left: TreeNode?
  var right: TreeNode?
  
  init(val: Int) {
    self.val = val
    self.left = nil
    self.right = nil
  }
}

递归法

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

  var result = [Int]()
  result.append(root.val)
  let leftResult = preorderTraversal(root.left)
  let rightResult = preorderTraversal(root.right)
  result.append(contentsOf: leftResult)
  result.append(contentsOf: rightResult)
  return result
}

借用栈遍历

树之所以要用栈，是因为下去了就没法上去，所以一种是保存父亲节点，也就是一路沿着左边压栈，回头了就弹出父亲，再走别的路。

还有一种是直接把右路压进去，到时候回头时连父节点都省略了。

左路入栈：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func preorderTraversal(_ root: TreeNode?) -> [Int] {
  var res = [Int]()
  var cur = root
  var stack = [TreeNode]()
  while cur !== nil || !stack.isEmpty {
    while cur != nil {
      res.append(cur!.val)
      stack.append(cur!)
      cur = cur?.left
    }
    cur = stack.popLast()
    cur = cur?.right
  }
  return res
}

左右路入栈：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func preorderTraversal(_ root: TreeNode?) -> [Int] {
  guard root !== nil else {
    return []
  }
  var res = [Int]()
  var stack: [TreeNode] = [root!]
  while !stack.isEmpty {
    let cur = stack.popLast()
    res.append(cur!.val)
    
    if let right = cur?.right {
      stack.append(right)
    }
    if let left = cur?.left {
      stack.append(left)
    }
  } 
  return res
}