亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

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

wangbjun / 1309人閱讀

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

題目描述

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

輸入描述: 
        1                    1
       /                   / 
      2   3    ——————>     3   2
     /  /               /  / 
    4  5 6  7            7  6 5  4
解題思路

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

分解問(wèn)題后的子問(wèn)題是什么，也就是重復(fù)的那一部分是什么？

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

回到翻轉(zhuǎn)二叉樹(shù)的問(wèn)題，我們梳理一遍整個(gè)翻轉(zhuǎn)過(guò)程：

root開(kāi)始，交換root的left元素和root.right元素
root.left開(kāi)始，交換root.left.left元素和root.left.right元素
root.right開(kāi)始，交換root.right.left元素和root.right.right元素
...
...

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

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

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

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

非遞歸版本
非遞歸版本可以從樹(shù)的層次遍歷上找到靈感，無(wú)非就是按照層來(lái)遍歷樹(shù)的節(jié)點(diǎn)，且一邊遍歷一邊交換當(dāng)前節(jié)點(diǎn)的左右子節(jié)點(diǎn)，直到遍歷完畢就OK

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

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/95508.html

相關(guān)文章

  • 【刷算法】求二叉樹(shù)深度的遞歸以及非遞歸解法

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

    Carl 評(píng)論0 收藏0

  • 【刷算法】判斷二叉搜索樹(shù)的后序遍歷序列的遞歸實(shí)現(xiàn)和非遞歸實(shí)現(xiàn)

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

    Anshiii 評(píng)論0 收藏0

  • 前端也需要好好的精進(jìn)自己的算法

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

    hersion 評(píng)論0 收藏0

  • LeetCode 156 Binary Tree Upside Down 上下翻轉(zhuǎn)二叉樹(shù)

    摘要：翻轉(zhuǎn)以后如下解題思路翻轉(zhuǎn)的形式一開(kāi)始不是很清楚，但是里面的高票答案給了一個(gè)很好的解釋?？蠢?，樹(shù)的左邊最深的底層是，是新的。對(duì)于每個(gè)，將鏈接右孩子的指針去掉，將變?yōu)楫?dāng)前左孩子的，成為左孩子的。遞歸的寫(xiě)法遞歸調(diào)用得到新的，并且沿途改變結(jié)構(gòu)。 LeetCode 156 Binary Tree Upside Down Given a binary tree where all the rig...

    Loong_T 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<