【刷算法】翻轉(zhuǎn)二叉樹的遞歸和非遞歸解法

wangbjun 發(fā)布于2019-08-22 18:06 / 1263人閱讀

摘要：題目描述操作給定的二叉樹，將其變翻轉(zhuǎn)為源二叉樹的鏡像。輸入描述解題思路遞歸版本首先，對數(shù)據(jù)結(jié)構(gòu)比較了解的話會想到用遞歸來解決。所謂遞歸，在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法來自維基百科。

題目描述

操作給定的二叉樹，將其變翻轉(zhuǎn)為源二叉樹的鏡像。

輸入描述:

        1                    1
       /                   / 
      2   3    ——————>     3   2
     /  /               /  / 
    4  5 6  7            7  6 5  4

解題思路

遞歸版本
首先，對數(shù)據(jù)結(jié)構(gòu)比較了解的話會想到用遞歸來解決。
所謂遞歸，在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法（來自維基百科）。這個解釋還是比較教條的，對于工程師來說，首先要思考：

分解問題后的子問題是什么，也就是重復的那一部分是什么？

什么時候結(jié)束重復？即終止條件是什么

回到翻轉(zhuǎn)二叉樹的問題，我們梳理一遍整個翻轉(zhuǎn)過程：

root開始，交換root的left元素和root.right元素
root.left開始，交換root.left.left元素和root.left.right元素
root.right開始，交換root.right.left元素和root.right.right元素
...
...

可以看出來重復的部分是：交換X元素的left和right元素，用偽代碼表示為：

temp = X.left;
X.left = X.right;
X.right = temp;

那么終止條件是什么呢？很顯然是當元素為null時，它就談不上去交換左右子元素了，所以X=null時終止遞歸。
此時代碼就很好寫了：

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} 
function Mirror(root){
    // 終止條件
    if(root === null)
        return;
    // 重復操作的部分
    var temp = root.left;
    root.left = root.right;
    root.right = temp;
    //分別再對左右子節(jié)點進行同樣的操作
    Mirror(root.left);
    Mirror(root.right);
}

非遞歸版本
非遞歸版本可以從樹的層次遍歷上找到靈感，無非就是按照層來遍歷樹的節(jié)點，且一邊遍歷一邊交換當前節(jié)點的左右子節(jié)點，直到遍歷完畢就OK

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} 
function Mirror(root){
    if(root === null)
        return;
    var queue = [];// 隊列來輔助遍歷樹
    queue.push(root);

    while(queue.length !== 0) {
        var cur = queue.shift();// 彈出隊列頭的元素，交換它的左右子節(jié)點
        if(cur !== null) {
            var temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;
        
            queue.push(cur.left)// 左子節(jié)點入隊
            queue.push(cur.right);// 右子節(jié)點入隊
        }  
    }    
}

GPU云服務器云服務器非遞歸二叉樹遍歷二叉樹的遍歷二叉樹的存儲二叉樹的存儲結(jié)構(gòu)

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/95508.html

【刷算法】求二叉樹深度的遞歸以及非遞歸解法

摘要：題目描述輸入一棵二叉樹，求該樹的深度。遞歸解法非遞歸解法原來標識當前層是否遍歷完畢當前彈出元素為時，說明一層以及遍歷完畢了，所以最后一層的彈出時不能再往隊列里面加了題目描述輸入一棵二叉樹，求該樹的深度。從根結(jié)點到葉結(jié)點依次經(jīng)過的結(jié)點（含根、葉結(jié)點）形成樹的一條路徑，最長路徑的長度為樹的深度。遞歸解法 function TreeNode(x) { this.val = x;...

Carl 2019-08-22 18:13 評論0 收藏0
【刷算法】判斷二叉搜索樹的后序遍歷序列的遞歸實現(xiàn)和非遞歸實現(xiàn)

摘要：題目描述輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。那么對于二叉搜索樹的后序遍歷的序列來說，最后一個元素即是它的根節(jié)點，序列的前某部分元素全部小于最后一個元素，序列的后某部分元素全大于最后一個元素。題目描述輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設輸入的數(shù)組的任意兩個數(shù)字都互不相同。分析所謂二叉搜索...

Anshiii 2019-08-22 18:20 評論0 收藏0
前端也需要好好的精進自己的算法

摘要：算法前端發(fā)展的再快，也不要忘記精進自己的算法，算法是靈魂和核心。我會把我刷過的算法題總結(jié)歸類，不斷完善。算法前端發(fā)展的再快，也不要忘記精進自己的算法，算法是靈魂和核心。我會把我刷過的算法題總結(jié)歸類，不斷完善。歡迎大家關注。數(shù)組和堆棧數(shù)組去重旋轉(zhuǎn)數(shù)組如何快速找出兩個數(shù)之和等于某一個值的兩個數(shù)？快排排序算法大總結(jié) 快速找到數(shù)組中的最大值多維數(shù)組的展開二分查找有效的括...

hersion 2019-08-23 10:36 評論0 收藏0
LeetCode 156 Binary Tree Upside Down 上下翻轉(zhuǎn)二叉樹

摘要：翻轉(zhuǎn)以后如下解題思路翻轉(zhuǎn)的形式一開始不是很清楚，但是里面的高票答案給了一個很好的解釋。看例子，樹的左邊最深的底層是，是新的。對于每個，將鏈接右孩子的指針去掉，將變?yōu)楫斍白蠛⒆拥模蔀樽蠛⒆拥摹＿f歸的寫法遞歸調(diào)用得到新的，并且沿途改變結(jié)構(gòu)。 LeetCode 156 Binary Tree Upside Down Given a binary tree where all the rig...

Loong_T 2019-08-16 13:28 評論0 收藏0