背景
二叉树的遍历是学习二叉树数据结构的基础，不过学完之后，如果理解不深，是特别容易忘记的，查看了很多种实现后，整理了一些相对较为容易的写法。
其中： DFS：深度优先遍历，包括前序遍历，中序遍历，后序遍历 BFS：深度优先遍历，包括层序遍历
实现
首先定义一个基础的二叉树结点。
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init(_ val: Int) {
self.val = val
}
}
前序遍历
前序遍历，是指根结点在前，子树在后。 解决思路： 使用栈结构辅助
- 根结点先入栈
- 访问根节点，将右结点先入栈，然后左结点再入栈
- 循环到栈为空
func preorderTranversal(_ root: TreeNode?) -> [Int] {
guard let root = root else {
return []
}
var ret = [Int]()
var stack = [TreeNode]()
stack.append(root)
while !stack.isEmpty {
let popped = stack.removeLast()
ret.append(popped.val)
if let right = popped.right {
stack.append(right)
}
if let left = popped.left {
stack.append(left)
}
}
return ret
}
中序遍历
中序遍历，是指先遍历左子树，再遍历根结点，最后变量右子树。 思路： 使用栈结构辅助
- 一直向左直到最左的子结点，将所有的结点入栈
- 当到达最左结点时，pop 出栈进行访问
- 使用 pop 出栈元素的右子树，循环操作，直到栈为空
func inorderTraversal(_ root: TreeNode?) -> [Int] {
var stack = [TreeNode]()
var ret = [Int]()
var node = root
while node != nil || !stack.isEmpty {
while node != nil {
stack.append(node!)
node = node?.left
}
node = stack.removeLast()
ret.append(node!.val)
node = node?.right
}
return ret
}
后序遍历
后序遍历，是指先遍历左右子树，再访问根节点，左右中 解题思路： 左右中，反过来就是中右左，而中右左，相当于就是前序遍历了。
1
2
3
1
2 3
4 5
后序（左右中）：4 5 2 3 1 前序（中右左）：1 3 2 5 4
步骤：
- 前序遍历（中右左）
- 反转结果数组
func postOrderTranversal(_ root: TreeNode?) -> [Int] {
guard let root = root else {
return []
}
var stack = [TreeNode]()
var ret = [Int]()
stack.append(root)
while stack.count > 0 {
let popped = stack.removeLast()
ret.append(popped.val)
if let left = popped.left {
stack.append(left)
}
if let right = popped.right {
stack.append(right)
}
}
return ret.reversed()
}
层序遍历
层序遍历，是指根据树的层级进行遍历，因此遍历返回值是二维数组。 思路： 用队列结构辅助。
- 首层元素入队
- 遍历该层的元素（队列的 size），并让左右子结点依次入栈
- 直到队列为空
func levelTranversal2(_ root: TreeNode?) -> [[Int]] {
var ret = [[Int]]()
var queue = [TreeNode]()
if let root = root {
queue.append(root)
}
while queue.count > 0 {
let size = queue.count
var level = [Int]()
for _ in 0..<size {
let dequeue = queue.removeFirst()
level.append(dequeue.val)
if let left = dequeue.left {
queue.append(left)
}
if let right = dequeue.right {
queue.append(right)
}
}
ret.append(level)
}
return ret
}
小结
便于理解的思路更容易加深对学习的理解和兴趣，出于性能的考虑其实可以探索诸如 Morris 二叉树遍历的实现，称得上是“算法之美”。
