二叉树的遍历-Swift
对应在Leetcode中的题目：
- 前序遍历： 144
- 后序遍历： 145
- 中序遍历： 94
- 层次遍历：102
二叉树的结点结构
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init(_ val: Int) {
self.val = val
self.left = nil
self.right = nil
}
}
递归遍历
递归题目三要素写法
这里帮助大家确定下来递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！
1. 确定递归函数的参数和返回值：
确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2. 确定终止条件：
写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3. 确定单层递归的逻辑：
确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
前序递归
class Solution {
func preorderTraversal(_ root: TreeNode?) -> [Int] {
var result = [Int]()
traversal(root, &result)
return result
}
private func traversal(_ cur: TreeNode?, _ result: inout [Int]) {
guard let cur = cur else { return }
result.append(cur.val)
traversal(cur.left, &result)
traversal(cur.right, &result)
}
}
中序递归
class Solution {
func inorderTraversal(_ root: TreeNode?) -> [Int] {
var result = [Int]()
traversal(root, &result)
return result
}
func traversal(_ root: TreeNode?, _ result: inout [Int]) {
guard let cur = root else { return }
traversal(cur.left, &result)
result.append(cur.val)
traversal(cur.right, &result)
}
}
后序递归
class Solution {
func postorderTraversal(_ root: TreeNode?) -> [Int] {
var result = [Int]()
traversal(root, &result)
return result
}
private func traversal(_ cur: TreeNode?, _ result: inout [Int]) {
guard let element = cur else { return }
traversal(element.left, &result)
traversal(element.right, &result)
result.append(element.val)
}
}
非递归遍历
前序非递归
- 方法1：
func preorderTraversal(_ root: TreeNode?) -> [Int] {
guard let element = root else { return [] }
var result = [Int]()
var stack = [element]
while !stack.isEmpty {
let node = stack.removeLast()
result.append(node.val)
if let right = node.right {
stack.append(right)
}
if let left = node.left {
stack.append(left)
}
}
return result
}
- 方法2：
func preorderTraversal(_ root: TreeNode?) -> [Int] {
guard let element = root else { return [] }
var result = [Int]()
var stack = [TreeNode]()
// 初始化时指向element
var cur = root
// 循环条件：要么cur不空，要么stack不空
while cur != nil || !stack.isEmpty {
while cur != nil {
stack.append(cur!)
result.append(cur!.val)
cur = cur!.left
}
let node = stack.removeLast()
cur = node.right
}
return result
}
中序非递归
//中序非递归
//思路：通过stack 保存已经访问的元素，用于原路返回
func inorderTraversal(_ root: TreeNode?) ->[Int] {
guard root != nil else { return [] }
var result = [Int]()
var stack = [TreeNode]()
var cur = root
while cur != nil || stack.count != 0 {
while cur != nil {
stack.append(cur!)
cur = cur!.left
}
let node = stack.removeLast()
result.append(node.val)
cur = node.right
}
return result
}
后序非递归
- 方法1
func postorderTraversal(_ root: TreeNode?) -> [Int] {
guard let element = root else { return [] }
var result = [Int]()
var stack = [element]
// 按中右左的顺序访问，然后逆序输出即为后序遍历
while !stack.isEmpty {
let topNode = stack.removeLast()
result.append(topNode.val)
if topNode.left != nil {
stack.append(topNode.left!)
}
if topNode.right != nil {
stack.append(topNode.right!)
}
}
//反转
result.reverse()
return result
}
- 方法2
func postorderTraversal(_ root: TreeNode?) -> [Int] {
guard root != nil else { return [] }
var result = [Int]()
var stack = [TreeNode]()
//lastVisit标识上次（刚刚访问的结点）
var lastVisit: TreeNode?
var cur = root
while cur != nil || !stack.isEmpty {
while cur != nil {
stack.append(cur!)
cur = cur!.left
}
//现在cur指向nil
//现在栈顶是最左结点，无需访问更左，如果没有右孩子或者右孩子刚访问过，则访问自身
let top = stack.last!//这里先看看，先不弹出
if top.right == nil || top.right === lastVisit {//注意是===全等，==用于判断值相等并且需要遵循Equatable协议
let node = stack.removeLast()
result.append(node.val)
lastVisit = node
}else{
cur = top.right
}
}
return result
}