溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

python對稱二叉樹該如何理解

發(fā)布時間：2021-12-13 16:35:24 來源：億速云 閱讀：136 作者：柒染 欄目：大數(shù)據(jù)

這期內(nèi)容當中小編將會給大家?guī)碛嘘P(guān)python對稱二叉樹該如何理解，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

題目描述

給定一個二叉樹，檢查它是否是鏡像對稱的。

例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。

    1   / \  2   2 / \ / \3  4 4  3
 

但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:

    1   / \  2   2   \   \   3    3


解題方案

 

思路

  • 標簽：dfs

  • 遞歸結(jié)束條件：

    • 都為空指針則返回true

    • 只有一個為空則返回false

  • 遞歸過程：

    • 判斷兩個指針當前節(jié)點值是否相等

    • 判斷A的右子樹與B的左子樹是否對稱

    • 判斷A的左子樹與B的右子樹是否對稱

  • 短路：在遞歸判斷過程中存在短路現(xiàn)象，也就是做與操作時，如果前面的值返回false則后面的不再進行計算

  • 時間復(fù)雜度：O(n)

python對稱二叉樹該如何理解  
算法動圖
 

代碼

class Solution {    public boolean isSymmetric(TreeNode root) {        return isMirror(root, root);    }
    public boolean isMirror(TreeNode t1, TreeNode t2) {        if (t1 == null && t2 == null) return true;        if (t1 == null || t2 == null) return false;        return (t1.val == t2.val)            && isMirror(t1.right, t2.left)            && isMirror(t1.left, t2.right);    }}
    

上述就是小編為大家分享的python對稱二叉樹該如何理解了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道。

向AI問一下細節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手