前言
本篇整理二叉樹相關(guān)算法的Swift實(shí)現(xiàn)裙椭，實(shí)現(xiàn)方法一部分來自網(wǎng)絡(luò)，一部分筆者自己編寫署浩。由于水平有限揉燃，出現(xiàn)錯誤還請見諒。
一筋栋、遍歷
二叉樹的遍歷方式分為前序炊汤、中序和后序三種。三種遍歷方式都可以通過遞歸實(shí)現(xiàn)弊攘，也可以通過循環(huán)實(shí)現(xiàn)抢腐。下面給出Swift版本的實(shí)現(xiàn)代碼：
1.1 前序遍歷
遞歸實(shí)現(xiàn)：
//: 前序遍歷，遞歸實(shí)現(xiàn)
func preOrderTraversal_RE(root: TreeNode?) -> [Int] {
var res = [Int]()
_preHelper(root, &res)
return res
}
// 輔助方法
func _preHelper(_ node: TreeNode?, _ res: inout [Int]) {
guard let node = node else {return}
res.append(node.val)
_preHelper(node.left, &res)
_preHelper(node.right, &res)
}
非遞歸實(shí)現(xiàn)：
func preOrderTraversal(root: TreeNode?) -> [Int] {
var res = [Int]()
var stack = [TreeNode]() //輔助棧襟交，存放節(jié)點(diǎn)氓栈。
var node = root
while !stack.isEmpty || node != nil {
if node != nil {
res.append(node!.val)
stack.append(node!)
node = node!.left
} else {
node = stack.removeLast().right
}
}
return res
}
1.2 中序遍歷
遞歸實(shí)現(xiàn)：
//: 中序遍歷，遞歸實(shí)現(xiàn)
func inOrderTraversal_RE(root: TreeNode?) -> [Int] {
var nums = [Int]()
_inHelper(root, &nums)
return nums
}
// 輔助方法
func _inHelper(_ node: TreeNode?, _ nums: inout [Int]) {
guard let node = node else {return}
_inHelper(node.left, &nums)
nums.append(node.val)
_inHelper(node.right, &nums)
}
非遞歸實(shí)現(xiàn)：
//: 中序遍歷, 非遞歸實(shí)現(xiàn)
func inOrderTraversal(root: TreeNode?) -> [Int] {
var res = [Int]()
var stack = [TreeNode]()
var node = root
while !stack.isEmpty || node != nil {
if node != nil {
stack.append(node!)
node = node!.left
} else {
node = stack.removeLast()
res.append(node!.val)
node = node!.right
}
}
return res
}
1.3 后序遍歷
遞歸實(shí)現(xiàn)：
//: 后序遍歷遞歸
func postOrderTraversal_RE(_ root: TreeNode?) -> [Int] {
var nums = [Int]()
_postHelper(root, &nums)
return nums
}
func _postHelper(_ node: TreeNode?, _ nums:inout [Int]){
guard let node = node else {return}
_postHelper(node.left, &nums)
_postHelper(node.right, &nums)
nums.append(node.val)
}
非遞歸實(shí)現(xiàn)
//: 后序遍歷
func postOrderTraversal(root: TreeNode?) -> [Int] {
var res = [Int]()
var stack = [TreeNode]()
var tagStack = [Int]()
var node = root
while !stack.isEmpty || node != nil {
while node != nil {
stack.append(node!)
tagStack.append(0)
node = node!.left
}
while !stack.isEmpty && tagStack.last! == 1 {
tagStack.removeLast()
res.append(stack.removeLast().val)
}
// 訪問左子樹到頭婿着，訪問右子樹
if !stack.isEmpty {
tagStack.removeLast()
tagStack.append(1)
node = stack.last!.right
}
}
return res
}
二授瘦、二叉樹的深度
//: 計算樹的最大深度
func maxDepth(root: TreeNode?) -> Int {
guard let root = root else { return 0 }
return max(maxDepth(root: root.left), maxDepth(root: root.right)) + 1
}
三、二叉樹廣度優(yōu)先遍歷
//: 層次遍歷竟宋，廣度優(yōu)先遍歷提完，需要使用隊(duì)列
func levelOrder(root: TreeNode?) -> [[Int]] {
var res = [[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 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
}
四、判斷是否為二叉搜索樹
//: 判斷是否是二叉搜索樹
func isValidBST(root: TreeNode?) -> Bool {
return _helper(root, nil, nil)
}
private func _helper(_ node: TreeNode?, _ min: Int?, _ max: Int?) -> Bool {
guard let node = node else { return true }
// 所有右子樹的節(jié)點(diǎn)值大于根節(jié)點(diǎn)
if let min = min, node.val <= min {
return false
}
// 所有左子樹的節(jié)點(diǎn)值小于根節(jié)點(diǎn)
if let max = max, node.val >= max {
return false
}
return _helper(node.left, min, node.val) && _helper(node.right, node.val, max)
}
未完待續(xù)ing
五丘侠、小結(jié)
源碼地址：BinaryTree
