实现二叉树结点
class BinaryTreeNode {
let val: Int
var left: BinaryTreeNode?
var right: BinaryTreeNode?
public init(_ val: Int, left: BinaryTreeNode? = nil, right: BinaryTreeNode? = nil) {
self.val = val
self.left = left
self.right = right
}
}
构造二叉树
let treeNode5 = BinaryTreeNode(5)
let treeNode4 = BinaryTreeNode(4)
let treeNode3 = BinaryTreeNode(3)
let treeNode2 = BinaryTreeNode(2,left: treeNode5)
let treeNode1 = BinaryTreeNode(1,left: treeNode3,right: treeNode4)
let rootNode = BinaryTreeNode(0,left: treeNode1,right: treeNode2)
image.png
前序遍历
给定一个节点，先遍历该节点，然后遍历左子树，然后右子树
func preorder(_ root: BinaryTreeNode?, _ list: inout [Int]) {
guard let root = root else {
return
}
list.append(root.val)
preorder(root.left, &list)
preorder(root.right, &list)
}
前序遍历.png
中序遍历
给定一个节点，先遍历左子树，再遍历当前结点，然后右子树
func inorder(_ root: BinaryTreeNode?, _ list: inout [Int]) {
guard let root = root else {
return
}
inorder(root.left, &list)
list.append(root.val)
inorder(root.right, &list)
}
中序遍历.png
后序遍历
给定一个节点，先遍历左子树，再遍历右子树，然后当前结点
func postOrder(_ root: BinaryTreeNode?, _ list: inout [Int]) {
guard let root = root else {
return
}
postOrder(root.left, &list)
postOrder(root.right, &list)
list.append(root.val)
}
后序遍历.png
层序遍历
顾名思义，一层一层的遍历，借助队列的属性实现，
1.将根节点入队
2.依次将队列的元素出队，判断是否有左右节点，将左右节点入队，并且将当前出队的结点值加入数组中
3.继续下一次的入队，左右节点入队，加入值到数组中
func levelorder(_ root: BinaryTreeNode?, _ list: inout [Int], _ queue: inout Queue<Any>) {
guard let root = root else {
return
}
//root节点入队
queue.enQueue(item: root)
while !queue.empty() {
var perLevelVal = [Int]()//每层节点的值
for _ in 0..<queue.count() {
let top = queue.deQueue() as! BinaryTreeNode //将当前节点出队
if let left = top.left {
queue.enQueue(item: left) //left节点入队
}
if let right = top.right {
queue.enQueue(item: right) //right节点入队
}
perLevelVal.append(top.val) //当前节点的值加入数组
}
list.append(contentsOf: perLevelVal)
}
}
leetcode原题
107. 二叉树的层序遍历 II
还是按照队列的特性遍历，注意要把数据插入到最前面，因为题目要求的是倒序
func levelOrderBottom(_ root: TreeNode?) -> [[Int]] {
guard let root = root else {
return []
}
var queue = [TreeNode?]()
var res = [[Int]]()
queue.append(root)
while !queue.isEmpty {
let count = queue.count
var perLevelList = [Int]()
for _ in 0..<count {
guard let node = queue.removeFirst() else {
continue
}
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
perLevelList.append(node.val)
}
res.insert(perLevelList, at: 0)
}
return res
}
116. 填充每个节点的下一个右侧节点指针
进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
因此首先想到的是用递归的方式，
image.png
解题思路：
某个节点比如这里从1开始看，1的next是nil，1的left2，right3
left2的next计算公式为：
left2.next=right3。
而2的right5的next计算公式为：
right5.next=left2.next.left
概括一下就是：
给定一个节点A，A的next=节点B，A的左子节点的next等于A的右子节点。而A的右子节点的next等于节点B的左子节点，依次递归每一个节点，直到节点为空即可（可以看出每次节点的关系）
/**
* Definition for a Node.
* public class Node {
* public var val: Int
* public var left: Node?
* public var right: Node?
* public var next: Node?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* self.next = nil
* }
* }
*/
class Solution {
func connect(_ root: Node?) -> Node? {
guard let root = root else {
return nil
}
root.left?.next = root.right
if let next = root.next {
root.right?.next = next.left
}
connect(root.left)
connect(root.right)
return root
}
}
用层序遍历也可以实现，但是空间复杂度就不会是常量级
117. 填充每个节点的下一个右侧节点指针 II
116题的二叉树是完美二叉树，即每个节点都有左右节点。
但是本题给的条件是二叉树，要注意考虑到多种情况，
比如下面的
image.png
所以再用普通的递归方式不适用，通过依次查找next的方式进行链接
@discardableResult
func connect(_ root: Node?) -> Node? {
guard let root = root else {
return nil
}
if root.left != nil {
if root.right != nil {
//有右节点直接赋值
root.left?.next = root.right
} else {
//没有右节点，查找next节点
root.left?.next = findNextNode(root:root.next)
}
}
if root.right != nil {
//赋值右节点的值
root.right?.next = findNextNode(root: root.next)
}
connect(root.right)
connect(root.left)
return root
}
//通过每层节点的链表依次查找，next节点右left则返回，没有返回right，都没有继续查找下一个next，直到查找完成
@discardableResult
private func findNextNode(root: Node?) -> Node? {
guard let root = root else {
return nil
}
if let left = root.left {
return left
}
if let right = root.right {
return right
}
if let next = root.next {
return findNextNode(root: next)
}
return nil
}
应该注意的是，这里为什么要先遍历右节点，
借用力扣上的回答，就是先保证右侧节点已经链接成功，
image.png
image.png
