迭代
前序遍历
根据栈的属性对二叉树进行遍历，注意先右节点入栈，随后左节点入栈
1.根节点入栈
2.当栈不为空时，栈顶元素出栈，如果栈顶元素右节点不为空，右节点入栈，如果左节点不为空，左节点入栈，
3.将当前出栈的栈顶元素的值加入数组
//二叉树的前序遍历
func stackPreorder(root: TreeNode?) -> [Int] {
var list = [Int]()
guard root != nil else {
return list
}
var stack = Stack()
//1.根节点入栈
stack.push(root)
while !stack.isEmpty {
//2.栈顶元素出栈
if let temp = stack.pop() {
//右节点入栈
if temp.right != nil {
stack.push(temp.right)
}
//左节点入栈
if temp.left != nil {
stack.push(temp.left)
}
//3.添加栈顶元素的值到数组
list.append(temp.val)
}
}
return list
}
中序遍历
1.指针cur不断向左移动，并且依次入栈
2.直到cur为空，开始出栈，依次将出栈元素加入到数组，
3.最后将cur指向出栈元素的right指针，迭代执行上述操作
func stackInOrder(root: TreeNode?) -> [Int] {
var list = [Int]()
guard root != nil else {
return list
}
var cur: TreeNode?
var stack = Stack()
cur = root
while !stack.isEmpty || cur != nil {
//1.向左移动，依次入栈
while cur != nil {
stack.push(cur)
cur = cur?.left
}
//2.cur为空，开始出栈。
if let temp = stack.pop() {
list.append(temp.val)
//3.指针cur指向右子树
cur = temp.right
}
}
return list
}
后序遍历
1.定义cur指针（当前遍历的节点）和pre指针（上一次遍历的节点）
2.指针cur不断向左移动，并且依次入栈
3.直到cur为空，开始出栈，cur指向出栈的元素
4.判断cur.right == nil和cur.right == pre
（1）、当cur.right == nil说明cur没有右节点需要遍历，val直接加入list即可；当cur.right == pre，说明cur的右节点已经遍历过，同样加入list即可
（2）、当cur.right ！= nil说明cur有右节点需要遍历，因此再次将cur节点入栈，并且把cur指向它的右节点cur = cur.right
总结：从根节点开始到左子节点依次入栈，随后出栈并遍历出栈元素，发现有右子节点时（当发现右节点已被遍历时，就不遍历），将当前出栈元素重新入栈，继而遍历右节点，循环执行前述步骤
func stackLaOrder(root: TreeNode?) -> [Int] {
var list = [Int]()
guard root != nil else {
return list
}
//1.定义cur和pre指针
var cur: TreeNode? = root
var pre: TreeNode?
var stack = Stack()
while !stack.isEmpty || cur != nil {
//2.cur向左移动，入栈
while cur != nil {
stack.push(cur)
cur = cur?.left
}
//3.cur此时为空，开始出栈
cur = stack.pop()
if cur != nil {
//4.（1）当前出栈元素没有右节点或者右节点已被遍历完成
if cur!.right == nil || cur?.right == pre {
list.append(cur!.val)
pre = cur
cur = nil
} else {
//（2）当前出栈元素右节点没有被遍历，将当前元素重新入栈，并开始遍历右节点
stack.push(cur)
cur = cur?.right
}
}
}
return list
}
Morris
Morris遍历原则
当前节点定义为cur
- cur无左孩子，cur右移(cur = cur.right)
- cur有左孩子，找到cur左子树上的最右节点，记作mostRight
- mostRight无右节点，mostRight.right = cur，cur左移(cur = cur.left)
- mostRight有右节点，mostRight.right = nil，cur右移(cur = cur.right)
注意：查找cur左子树上的最右节点时应该判断不等于cur
Morris遍历实质
建立一种机制，对于没有左子树的节点只到达一次，对于有左子树的节点会到达两次
二叉树.png
前序遍历
1.节点cur的左节点为空，添加cur的值到数组，并右移
2.cur左节点不为空就查找最右节点mostRight，如果mostRight的右节点为空，就指定mostRight.right=cur并添加cur的值到数组，cur左移；如果mostRight的右节点不为空，就指定mostRight.right=nil，cur右移
具体流程⬇️：
1.cur=1，左孩子=2，找到2的的最右节点mostRight=5，mostRight.right=nil，所以5.right=1，cur左移cur = 1.left
2.cur=2，左孩子=4，找到4的的最右节点mostRight=9，mostRight.right=nil，所以9.right=2，cur左移cur = 2.left
3.cur=4，左孩子=8，找到8的的最右节点mostRight=8，mostRight.right=nil，所以8.right=4，cur左移cur = 4.left
4.cur=8，无左孩子，所以cur右移，cur=8.right(注意第3步8的右节点已经是4了)
5.cur=4，有左孩子=8，找到8的的最右节点mostRight=4，所以使8.right=nil，并且cur右移cur = 4.right
6.cur=9，无左孩子，所以cur右移，cur=9.right(注意第2步9的右节点已经是2了）
7.cur=2，左孩子=4，找到4的的最右节点mostRight=9，所以使9.right=nil，并且cur右移cur = 2.right
....
func morrisPerorder(root: TreeNode?) -> [Int] {
var list = [Int]()
guard root != nil else {
return list
}
var cur = root
var mostRight: TreeNode?
while cur != nil {
mostRight = cur?.left
if mostRight != nil { //有左孩子
//查找最右节点
while mostRight?.right != nil && mostRight?.right != cur {
mostRight = mostRight?.right
}
if mostRight?.right == nil {//最右节点的right=nil，所以mostRight.right=cur，cur左移
if let val = cur?.val {
list.append(val)
}
mostRight?.right = cur
cur = cur?.left
} else {//最右节点的right!=nil，所以mostRight.right=nil，cur右移
mostRight?.right = nil
cur = cur?.right
}
} else { //无左孩子，右移
list.append(cur!.val)
cur = cur?.right
}
}
return list
}
中序遍历
1.节点cur的左节点为空，添加cur的值到数组，并右移
2.cur左节点不为空就查找最右节点mostRight，如果mostRight的右节点为空，就指定mostRight.right=cur，cur左移并退出此次循环；如果mostRight的右节点不为空，就指定mostRight.right=nil，cur右移并添加cur的值到数组
func morrisInOrder(root: TreeNode?) -> [Int] {
var list = [Int]()
guard root != nil else {
return list
}
var cur:TreeNode? = root
var mostRight: TreeNode?
while cur != nil {
mostRight = cur!.left
if mostRight != nil {
while mostRight!.right != nil && mostRight!.right != cur {
mostRight = mostRight!.right
}
if mostRight!.right == nil {//右节点为空，指定右节点=cur，左移cur并退出此次循环
mostRight!.right = cur
cur = cur!.left
continue
} else {
mostRight!.right = nil//右节点不为空，指定右节点=nil，
}
}
list.append(cur!.val)
cur = cur?.right
}
return list
}
后序遍历
morris后序遍历和中序遍历相似，区别在于⬇️
1.节点cur的左节点为空时，只需要右移cur(cur = cur.right)
2.cur的左节点不为空时候查找最右节点mostRight，如果mostRight的右节点不为空除了将mostRight.right=nil外，进行反转链表并遍历
3.最后记得还要反转根节点为头部的链表并遍历
具体流程⬇️：
....前面省略
1.当cur=4，左孩子=8，mostRight=8，mostRight.right = 4，所以将mostRight.right=nil，并反转遍历以cur.left(也就是8)为head链表，然后右移cur
2.cur=9，无左孩子，右移
3.cur=2，左孩子=4，mostRight=9，mostRight.right = 2，所以将mostRight.right=nil，并反转遍历以cur.left(也就是4)为head链表，然后右移cur
.
.
.
最后一步，是将以1为head的(1->3->7)链表反转遍历完成
func morrisPostorder(root: TreeNode?) -> [Int]? {
guard root != nil else {
return nil
}
var list = [Int]()
var cur: TreeNode? = root
var mostRight: TreeNode?
while cur != nil {
mostRight = cur?.left
if mostRight != nil {
while mostRight?.right != nil && mostRight?.right != cur {
mostRight = mostRight?.right
}
if mostRight?.right == nil {
mostRight?.right = cur
cur = cur?.left
continue
} else {
mostRight?.right = nil
traverseReverse(cur?.left, &list)
}
}
cur = cur?.right
}
//以根节点为起点的链表
traverseReverse(root, &list)
return list
}
func traverseReverse(_ head: TreeNode?,_ list: inout [Int]) {
//翻转链表
let reverseNode = reverseList(head: head)
var cur = reverseNode
//从后往前遍历
while cur != nil {
list.append(cur!.val)
cur = cur?.right
}
//最后记得反转回来
_ = reverseList(head: reverseNode)
}
func reverseList(head: TreeNode?) -> TreeNode? {
guard head != nil else {
return nil
}
var cur = head
var pre: TreeNode?
while cur != nil {
let next = cur?.right
cur?.right = pre
pre = cur
cur = next
}
return pre
}
网友评论