二叉树
前序遍历:先访问根节点,再前序遍历左子树,再前序遍历右子树 中序遍历:先中序遍历左子树,再访问根节点,再中序遍历右子树 后序遍历:先后序遍历左子树,再后序遍历右子树,再访问根节点
注意点
- 以根访问顺序决定是什么遍历
- 左子树都是优先右子树
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
}
}
//前序递归
func preorderTraversal(_ root: TreeNode?) {
guard let element = root else { return }
// 先访问根再访问左右
print(element.val)
preorderTraversal(element.left)
preorderTraversal(element.right)
}
//前序非递归a
func preorderTraversal_a(_ 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 {
// 前序遍历,所以先保存结果
result.append(cur!.val)
stack.append(cur!)
cur = cur!.left
}
// pop
let node = stack.removeLast()
cur = node.right
}
return result
}
//前序非递归b
func preorderTraversal_b(_ 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
}
//中序非递归
//思路:通过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
}
// if let node = stack.popLast() {
let node = stack.removeLast()
result.append(node.val)
cur = node.right
// }
}
return result
}
//后序非递归a
func postorderTraversal_a(_ root: TreeNode?) ->[Int] {
guard root != nil else { return [] }
var result = [Int]()
var stack = [TreeNode]()
var lastVisit : TreeNode? // 通过lastVisit标识右子节点是否已经弹出
var cur = root
while cur != nil || stack.count != 0 {
while cur != nil {
stack.append(cur!)
cur = cur!.left
}
let top = stack.last!//这里先看看,先不弹出
if top.right == nil || top.right === lastVisit {//根节点必须在右节点弹出之后,再弹出
let node = stack.removeLast()
result.append(node.val)
lastVisit = node// 标记当前这个节点已经弹出过
}else{
cur = top.right
}
}
return result
}
//后序非递归b
func postorderTraversal_b(_ root: TreeNode?) ->[Int] {
guard let element = root else { return [] }
var result = [Int]()
var stack = [element]
var resultStack = [TreeNode]()
while !stack.isEmpty {
let node = stack.removeLast()
resultStack.append(node)
if let left = node.left{
stack.append(left)
}
if let right = node.right{
stack.append(right)
}
}
while !resultStack.isEmpty {
result.append(resultStack.removeLast().val)
}
return result
}
注意点
- 核心就是:根节点必须在右节点弹出之后,再弹出
func preorderTraversal_dfs(root: TreeNode?) -> [Int] {
var result = [Int]()
dfs(root, &result)
return result
}
// V1:深度遍历,结果指针作为参数传入到函数内部
func dfs(_ root: TreeNode?,_ result: inout [Int]) {
guard let node = root else { return }
result.append(node.val)
dfs(node.left, &result)
dfs(node.right, &result)
}
// V2:通过分治法遍历
func preorderTraversal_dfs_a(root: TreeNode?) -> [Int] {
let result = divideAndConquer(root)
return result
}
func divideAndConquer(_ root: TreeNode?) -> [Int] {
guard let node = root else { return [] }
var result = [Int]()
// 分治(Divide)
let left = divideAndConquer(node.left)
let right = divideAndConquer(node.right)
// 合并结果(Conquer)
result.append(node.val)
result.append(contentsOf: left)
result.append(contentsOf: right)
return result
}
注意点:
DFS 深度搜索(从上到下) 和分治法区别:前者一般将最终结果通过指针参数传入,后者一般递归返回结果最后合并
func levelOrder(_ root: TreeNode?) -> [[Int]] {
guard root != nil else { return [] }
var queue = [root!]
var res = [[Int]]()
while !queue.isEmpty {
let count = queue.count // 记录当前层有多少元素(遍历当前层,再添加下一层)
var level = [Int]() //存放该层所有数值
for _ in 0..<count {
let node = queue.removeFirst()// 出队列
level.append(node.val)
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
}
res.append(level)
}
return res
}