二叉樹算法總結(jié)

迭代

前序遍歷

根據(jù)棧的屬性對二叉樹進(jìn)行遍歷，注意先右節(jié)點(diǎn)入棧，隨后左節(jié)點(diǎn)入棧
1.根節(jié)點(diǎn)入棧
2.當(dāng)棧不為空時，棧頂元素出棧，如果棧頂元素右節(jié)點(diǎn)不為空，右節(jié)點(diǎn)入棧，如果左節(jié)點(diǎn)不為空，左節(jié)點(diǎn)入棧，
3.將當(dāng)前出棧的棧頂元素的值加入數(shù)組

    //二叉樹的前序遍歷
    func stackPreorder(root: TreeNode?) -> [Int] {
        var list = [Int]()
        guard root != nil else {
            return list
        }
        
        var stack = Stack()
        
        //1.根節(jié)點(diǎn)入棧
        stack.push(root)
        
        while !stack.isEmpty {
            //2.棧頂元素出棧
            if let temp = stack.pop() {
                //右節(jié)點(diǎn)入棧
                if temp.right != nil {
                    stack.push(temp.right)
                }
                
                //左節(jié)點(diǎn)入棧
                if temp.left != nil {
                    stack.push(temp.left)
                }
                
                //3.添加棧頂元素的值到數(shù)組
                list.append(temp.val)
            }
        }
        return list
    }

中序遍歷

1.指針cur不斷向左移動，并且依次入棧
2.直到cur為空，開始出棧，依次將出棧元素加入到數(shù)組，
3.最后將cur指向出棧元素的right指針，迭代執(zhí)行上述操作

    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指針（當(dāng)前遍歷的節(jié)點(diǎn)）和pre指針（上一次遍歷的節(jié)點(diǎn)）
2.指針cur不斷向左移動，并且依次入棧
3.直到cur為空，開始出棧，cur指向出棧的元素
4.判斷cur.right == nil和cur.right == pre
（1）、當(dāng)cur.right == nil說明cur沒有右節(jié)點(diǎn)需要遍歷，val直接加入list即可；當(dāng)cur.right == pre，說明cur的右節(jié)點(diǎn)已經(jīng)遍歷過，同樣加入list即可
（2）、當(dāng)cur.right ！= nil說明cur有右節(jié)點(diǎn)需要遍歷，因此再次將cur節(jié)點(diǎn)入棧，并且把cur指向它的右節(jié)點(diǎn)cur = cur.right
總結(jié)：從根節(jié)點(diǎn)開始到左子節(jié)點(diǎn)依次入棧，隨后出棧并遍歷出棧元素，發(fā)現(xiàn)有右子節(jié)點(diǎn)時（當(dāng)發(fā)現(xiàn)右節(jié)點(diǎn)已被遍歷時，就不遍歷），將當(dāng)前出棧元素重新入棧，繼而遍歷右節(jié)點(diǎn)，循環(huán)執(zhí)行前述步驟

   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）當(dāng)前出棧元素沒有右節(jié)點(diǎn)或者右節(jié)點(diǎn)已被遍歷完成
                if cur!.right == nil || cur?.right == pre {
                    list.append(cur!.val)
                    pre = cur
                    cur = nil
                } else {
                    //（2）當(dāng)前出棧元素右節(jié)點(diǎn)沒有被遍歷，將當(dāng)前元素重新入棧，并開始遍歷右節(jié)點(diǎn)
                    stack.push(cur)
                    cur = cur?.right
                }
            }
        }
        return list
    }

Morris

這篇文章講得非常好

Morris遍歷原則

當(dāng)前節(jié)點(diǎn)定義為cur

  • cur無左孩子，cur右移(cur = cur.right)
  • cur有左孩子，找到cur左子樹上的最右節(jié)點(diǎn)，記作mostRight
    • mostRight無右節(jié)點(diǎn)，mostRight.right = cur，cur左移(cur = cur.left)
    • mostRight有右節(jié)點(diǎn)，mostRight.right = nil，cur右移(cur = cur.right)

注意：查找cur左子樹上的最右節(jié)點(diǎn)時應(yīng)該判斷不等于cur

Morris遍歷實質(zhì)

建立一種機(jī)制，對于沒有左子樹的節(jié)點(diǎn)只到達(dá)一次，對于有左子樹的節(jié)點(diǎn)會到達(dá)兩次

二叉樹.png

前序遍歷

1.節(jié)點(diǎn)cur的左節(jié)點(diǎn)為空，添加cur的值到數(shù)組，并右移
2.cur左節(jié)點(diǎn)不為空就查找最右節(jié)點(diǎn)mostRight，如果mostRight的右節(jié)點(diǎn)為空，就指定mostRight.right=cur并添加cur的值到數(shù)組，cur左移；如果mostRight的右節(jié)點(diǎn)不為空，就指定mostRight.right=nil，cur右移

具體流程??：

1.cur=1，左孩子=2，找到2的的最右節(jié)點(diǎn)mostRight=5，mostRight.right=nil，所以5.right=1，cur左移cur = 1.left
2.cur=2，左孩子=4，找到4的的最右節(jié)點(diǎn)mostRight=9，mostRight.right=nil，所以9.right=2，cur左移cur = 2.left
3.cur=4，左孩子=8，找到8的的最右節(jié)點(diǎn)mostRight=8，mostRight.right=nil，所以8.right=4，cur左移cur = 4.left
4.cur=8，無左孩子，所以cur右移，cur=8.right(注意第3步8的右節(jié)點(diǎn)已經(jīng)是4了)
5.cur=4，有左孩子=8，找到8的的最右節(jié)點(diǎn)mostRight=4，所以使8.right=nil，并且cur右移cur = 4.right
6.cur=9，無左孩子，所以cur右移，cur=9.right(注意第2步9的右節(jié)點(diǎn)已經(jīng)是2了）
7.cur=2，左孩子=4，找到4的的最右節(jié)點(diǎn)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 { //有左孩子
                
                //查找最右節(jié)點(diǎn)
                while mostRight?.right != nil && mostRight?.right != cur {
                    mostRight = mostRight?.right
                }
                
                if mostRight?.right == nil {//最右節(jié)點(diǎn)的right=nil，所以mostRight.right=cur，cur左移
                    if let val = cur?.val {
                        list.append(val)
                    }
                    mostRight?.right = cur
                    cur = cur?.left
                } else {//最右節(jié)點(diǎn)的right!=nil，所以mostRight.right=nil，cur右移
                    mostRight?.right = nil
                    cur = cur?.right
                }
            } else { //無左孩子，右移
                list.append(cur!.val)
                cur = cur?.right
            }
        }
        return list
    }

中序遍歷

1.節(jié)點(diǎn)cur的左節(jié)點(diǎn)為空，添加cur的值到數(shù)組，并右移
2.cur左節(jié)點(diǎn)不為空就查找最右節(jié)點(diǎn)mostRight，如果mostRight的右節(jié)點(diǎn)為空，就指定mostRight.right=cur，cur左移并退出此次循環(huán)；如果mostRight的右節(jié)點(diǎn)不為空，就指定mostRight.right=nil，cur右移并添加cur的值到數(shù)組

 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 {//右節(jié)點(diǎn)為空，指定右節(jié)點(diǎn)=cur，左移cur并退出此次循環(huán)
                    mostRight!.right = cur
                    cur = cur!.left
                    continue
                } else {
                    mostRight!.right = nil//右節(jié)點(diǎn)不為空，指定右節(jié)點(diǎn)=nil，
                }
            }
            list.append(cur!.val)
            cur = cur?.right
        }
        
        return list
    }

后序遍歷

這里講的很詳細(xì)

morris后序遍歷和中序遍歷相似，區(qū)別在于??
1.節(jié)點(diǎn)cur的左節(jié)點(diǎn)為空時，只需要右移cur(cur = cur.right)
2.cur的左節(jié)點(diǎn)不為空時候查找最右節(jié)點(diǎn)mostRight，如果mostRight的右節(jié)點(diǎn)不為空除了將mostRight.right=nil外，進(jìn)行反轉(zhuǎn)鏈表并遍歷
3.最后記得還要反轉(zhuǎn)根節(jié)點(diǎn)為頭部的鏈表并遍歷
具體流程??：
....前面省略
1.當(dāng)cur=4，左孩子=8，mostRight=8，mostRight.right = 4，所以將mostRight.right=nil，并反轉(zhuǎn)遍歷以cur.left(也就是8)為head鏈表，然后右移cur
2.cur=9，無左孩子，右移
3.cur=2，左孩子=4，mostRight=9，mostRight.right = 2，所以將mostRight.right=nil，并反轉(zhuǎn)遍歷以cur.left(也就是4)為head鏈表，然后右移cur
.
.
.
最后一步，是將以1為head的(1->3->7)鏈表反轉(zhuǎn)遍歷完成

    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
        }
        //以根節(jié)點(diǎn)為起點(diǎn)的鏈表
        traverseReverse(root, &list)
        return list
    }
    
    func traverseReverse(_ head: TreeNode?,_ list: inout [Int]) {
        //翻轉(zhuǎn)鏈表
        let reverseNode = reverseList(head: head)
        var cur = reverseNode
        
        //從后往前遍歷
        while cur != nil {
            list.append(cur!.val)
            cur = cur?.right
        }
        //最后記得反轉(zhuǎn)回來
        _ = 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
    }
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容