Go 刷 leetcode｜樹系列之對稱二叉樹

今天為大家講解 LeetCode 第 101 題，是一道關(guān)于二叉樹的題目。

題目描述

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

例如，二叉樹 [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

進(jìn)階：

你可以運用遞歸和迭代兩種方法解決這個問題嗎？

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/symmetric-tree 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解題思路

關(guān)于「樹」的題目，大多使用「遞歸」思想來解決。這道題的解題思路如下：

1.怎么判斷一棵樹是不是對稱二叉樹？答案：如果所給根節(jié)點，為空，那么是對稱。如果不為空的話，當(dāng)他的左子樹與右子樹對稱時，他對稱

2.那么怎么知道左子樹與右子樹對不對稱呢？在這我直接叫為左樹和右樹 答案：在左樹和右樹均不為空情況下，如果左樹的左孩子與右樹的右孩子對稱，左樹的右孩子與右樹的左孩子對稱，那么這個左樹和右樹就對稱。

仔細(xì)讀這句話，是不是有點繞？怎么感覺有一個功能A我想實現(xiàn)，但我去實現(xiàn)A的時候又要用到A實現(xiàn)后的功能呢？

當(dāng)你思考到這里的時候，遞歸點已經(jīng)出現(xiàn)了：遞歸點：我在嘗試判斷左樹與右樹對稱的條件時，發(fā)現(xiàn)其跟兩樹的孩子的對稱情況有關(guān)系。

想到這里，你不必有太多疑問，上手去按思路寫代碼，函數(shù)A（左樹，右樹）功能是返回是否對稱

定義 函數(shù)A（左樹，右樹），函數(shù)處理的邏輯如下：

先處理判斷：如果左樹和右樹均為空，肯定對稱返回真；

如果左樹和右樹只有一個為空，肯定不對稱返回假；

其他情況，判斷：左樹節(jié)點值等于右樹節(jié)點值 且 函數(shù)A（左樹的左子樹，右樹的右子樹），函數(shù)A（左樹的右子樹，右樹的左子樹）均為真 才返回真

代碼實現(xiàn)

//go
/**
?*?Definition?for?a?binary?tree?node.
?*?type?TreeNode?struct?{
?*?????Val?int
?*?????Left?*TreeNode
?*?????Right?*TreeNode
?*?}
?*/
func?isSymmetric(root?*TreeNode)?bool?{
????if?root?==?nil?{
????????return?true
????}
????return?partSym(root.Left,?root.Right)
}

func?partSym(left,?right?*TreeNode)?bool?{
????//?注意以下兩個if判斷順序不能反
????//?都為nil
????if?left?==?nil?&&?right?==?nil?{
????????return?true
????}
????//?只有一個為nil
????if?left?==?nil?||?right?==?nil?{
????????return?false
????}
????if?((left.Val?==?right.Val)?&&?partSym(left.Left,?right.Right)?&&?partSym(left.Right,?right.Left))?{
????????return?true
????}
????return?false
}

//java
class?Solution?{
????public?boolean?isSymmetric(TreeNode?root)?{
????????if?(root?==?null)?{
????????????return?true;
????????}
????????return?partSym(root.left,?root.right);
????}

????private?boolean?partSym(TreeNode?node1,?TreeNode?node2)?{
????????if?(node1?==?null?&&?node2?==?null)?{
????????????return?true;
????????}
????????if?(node1?==?null?||?node2?==?null?||?node1.val?!=?node2.val)?{
????????????return?false;
????????}
????????return?partSym(node1.left,?node2.right)?&&?partSym(node1.right,?node2.left);
????}
}

鄭重聲明：

所展示代碼已通過 LeetCode 運行通過，請放心食用～