成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

【刷算法】對稱的二叉樹

Forest10 / 3154人閱讀

摘要：題目描述請實現(xiàn)一個函數(shù)，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。分析一般關(guān)于二叉樹的題目，第一直覺是往遞歸上面靠，當(dāng)然了，本題適不適合還暫時不知道。

題目描述

請實現(xiàn)一個函數(shù)，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。

分析

一般關(guān)于二叉樹的題目，第一直覺是往遞歸上面靠，當(dāng)然了，本題適不適合還暫時不知道。
所謂鏡像二叉樹，舉個例子

    1                        1
   /                       /  
  2   3    ---鏡像--->     3    2
 /  /                        / 
4  5 6                      6 5  4

如上圖，這個二叉樹就不是對稱的。

    1                        1
   /                       /  
  2   2    ---鏡像--->     2    2
 /                       /      
4       4                4       4

可以看出來，對于一個節(jié)點p來說
如果它的left為空且right為空，則p的左右子樹對稱；
如果left不為空且right不為空，
如果left的值不等于right的值，p的左右子樹不對稱
否則遞歸檢查left.left和right.right、left.right和right.left，為什么是這兩對節(jié)點呢？因為作鏡像操作之后，剛好right.right會落到left.left的位置，right.left會落到left.right的位置，所以只要left.left和right.right、left.right和right.left對稱即可，后面的可以遞歸的檢查下去。

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function isSymmetrical(root)
{
    if (root === null)
        return true;
    return check(root.left, root.right);
}
function check(l,  r){
    if(l === null && r === null){
        return true;
    }
    else if(l !== null && r !== null){
        if(l.val !== r.val)
            return false;
        else
            return check(l.left, r.right)&&check(l.right, r.left);
    }
    else{
        return false;
    }
}

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/95671.html

相關(guān)文章

  • 使用JavaScript完成二叉樹的一些基本操作

    摘要：另外，由于篇幅有限，本篇的重點在于二叉樹的常見算法以及實現(xiàn)。常見的二叉樹實現(xiàn)代碼之前寫過相關(guān)的文章，是關(guān)于如何創(chuàng)建及遍歷二叉樹的，這里不再贅述。同時我們注意到，在二叉樹深度比較大的時候，我們光是比較左右是不夠的。 本篇為復(fù)習(xí)過程中遇到過的總結(jié)，同時也給準備面試的同學(xué)一份參考。另外，由于篇幅有限，本篇的重點在于二叉樹的常見算法以及實現(xiàn)。 常見的二叉樹實現(xiàn)代碼 之前寫過相關(guān)的文章，是關(guān)于如...

    YPHP 評論0 收藏0

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

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

    wangbjun 評論0 收藏0

  • 【刷算法】LeetCode.236-二叉樹的最近公共祖先

    摘要：給定一個二叉樹找到該樹中兩個指定節(jié)點的最近公共祖先。示例輸入輸出解釋節(jié)點和節(jié)點的最近公共祖先是節(jié)點。說明所有節(jié)點的值都是唯一的。 給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。 示例 1: 輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 輸出: 3 解釋: 節(jié)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3。 示例 ...

    Joonas 評論0 收藏0

  • JavaScript判斷對稱二叉樹

    摘要：參考自對稱的二叉樹公眾號秘密花園對稱二叉樹非對稱二叉樹實現(xiàn)思路判斷根節(jié)點相同左子樹的右節(jié)點和右子樹的左節(jié)點相同右子樹的左節(jié)點和左子樹的右節(jié)點相同步驟模擬一個對稱二叉樹和非對稱二叉樹對稱二叉樹非對稱二叉樹步驟利用遞歸實現(xiàn)對稱二叉樹判斷判斷兩個 參考自ConardLi： 《對稱的二叉樹》 公眾號： code秘密花園 對稱二叉樹: 8 / ...

    iliyaku 評論0 收藏0

發(fā)表評論

0條評論

Forest10

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<