【刷算法】對(duì)稱的二叉樹(shù)

Forest10 發(fā)布于2019-08-22 18:15 / 3145人閱讀

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

題目描述

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，用來(lái)判斷一顆二叉樹(shù)是不是對(duì)稱的。注意，如果一個(gè)二叉樹(shù)同此二叉樹(shù)的鏡像是同樣的，定義其為對(duì)稱的。

分析

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

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

如上圖，這個(gè)二叉樹(shù)就不是對(duì)稱的。

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

可以看出來(lái)，對(duì)于一個(gè)節(jié)點(diǎn)p來(lái)說(shuō)
如果它的left為空且right為空，則p的左右子樹(shù)對(duì)稱；
如果left不為空且right不為空，
如果left的值不等于right的值，p的左右子樹(shù)不對(duì)稱
否則遞歸檢查left.left和right.right、left.right和right.left，為什么是這兩對(duì)節(jié)點(diǎn)呢？因?yàn)樽麋R像操作之后，剛好right.right會(huì)落到left.left的位置，right.left會(huì)落到left.right的位置，所以只要left.left和right.right、left.right和right.left對(duì)稱即可，后面的可以遞歸的檢查下去。

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;
    }
}