刷題日記（3）Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

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

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Follow up: Solve it both recursively and iteratively.

解題思路

1. 以root為分界分為左子樹和右子樹

2. 比較左子樹的父親和右子樹的父親, 如果一樣則進行下一步, 不一樣則回傳

False, 下方的孫子孩子就被剪掉不用再比

3. 比較左子樹父親下一層的左孩子 跟 右子樹父親下一層的左孩子

4. 因為遞迴的關係會繼續比左子樹父親下下一層的左孫子 跟 右子樹父親下下一層的右孫子, 直到比到一者或兩者為null (回傳false/ true )

5. 比左子樹父親下下一層的左孫子 跟 右子樹父親下下一層的右孫子 已經比完回傳值(false/true), 接著比左子樹父親下下一層的右孫子 跟 右子樹父親下下一層的左孫子, 直到比到一者或兩者為null (回傳false/ true ) 同4

6. 各個孫子的值回傳給左孩子和右孩子 決定左孩子和右孩子的 True/False

7. 最後回傳 左孩子&&右孩子,( root只有在一開始設定base case=null回傳true時有用, 這裡不用管root)

解題方式

1. 分治法（使用遞歸）

遞迴的三種情況

1. 相比的兩個點皆為null, 則回傳 True

2. 一邊node 有值, 一邊沒有, 不對稱則回傳false

3. 兩個node都有值的狀況下, 如果值不相等則回傳false. 如果值相等則繼續比孩子直到第1種情況發生

(main function)

1. 如果傳進來的node為null, 則回傳true
2. 接著不為null, 則把root的左子樹跟右子樹傳到helper function裡

(isSymmetric)

3. 如果左邊leftRoot為null 以及 右邊rightRoot為null 則回傳 true

4. 如果其中一邊為null, 為不對稱則回傳 false

5. 如果左邊leftRoot值不等於右邊rightRoot值則回傳 false

6. 布林值 left 等於 呼叫(isSymmetric)傳入leftRoot的左孩子和rightRoot的右孩子（開始遞迴直到達到上方任一條件回傳true或false）

7. 布林值 right 等於 呼叫(isSymmetric)傳入leftRoot的右孩子和rightRoot的左孩子（開始遞迴直到達到上方任一條件回傳true或false）

8. 回傳 left && right (T&&F=F ; T&&T=T; F&F=F; F&&T=F)

以這個為例子

root不為null, 則把root的左子樹跟右子樹傳到helper function裡, left node和 right node值一樣,繼續往下

接著比兩者的孩子, 設一個 布林值 left ＝ 呼叫(isSymmetric)傳入leftRoot的左孩子和rightRoot的右孩子, Left1 為2的left遞迴第一層(也就是3)

由於呼叫(isSymmetric)的關係(遞迴) LeftRoot和RightRoot往下移動一層,繼續比LeftRoot和RightRoot的值, 因爲都等於3, 再設一個 布林值 left ＝ 呼叫(isSymmetric)傳入leftRoot的左孩子和rightRoot的右孩子（又一層遞迴）

此時的遞迴來到了第二層, 傳入的leftroot.next變成了leftroot 以及rightroot.next變成了right root. 此時遇到遞迴停止條件兩者為null則回傳true

由於第二層的遞迴的left已經完成, 繼續第二層的right遞迴,也是一樣遇到兩者為null條件回傳true

第二層的遞迴已經全部完成得到left是true, right也是true; 結束第二層遞迴回傳left && right 得到了true給第一層遞迴的left（也就是3）

此時2的left第一層遞迴和第二層遞迴已經完成, 準備開始2的right的第一層遞迴

開始第一層遞迴的right,相比值一樣, 接著（呼叫了isSymmetric）開始了第二層遞迴

第二層遞迴的left值(傳入leftRoot.left 和rightRoot.right 都為null), 得到第二層遞迴的left為true

第二層遞迴的right值(傳入leftRoot.right 和rightRoot.left 都為null), 得到第二層遞迴的right為true

第二層遞迴的left和right都完成也得到true, 所以回傳給第一層遞迴的right為true (也就是4)

2結束了left和right的孩子和孫子遞迴,得到了left和right皆為true, 因此回傳true

結束helper function回到main function, main function 最後回傳root.leftnode && root.rightnode 為true

不管root值為何,只要root.rightnode 和root.leftnode為true, 這顆就是對稱樹

總之,判斷一棵樹是不是對稱樹只要以root為分界線,然後判斷左子樹和右子樹是不是相等就好（因此其實應該也可以用 BFS解,之後有空再補）

（相比的順序和對應）

以這棵左子樹範例的相比順序是 ：父親(左孩子(左的左孫子-左的右孫子)右孩子（右的左孫子-右的右孫子））, 反正就是每一層就是父親先比然後一路往左先開始

＊Divide and conquer中文翻作分治法，概念如字面上的意義，將問題先切分成小問題後再解決，再將結果合併求出原始問題的答案。

以下摘錄自Wiki

分解：將原問題分解為若干個規模較小，相對獨立，與原問題形式相同的子問題。
解決：若子問題規模較小且易於解決時，則直接解。否則，遞歸地解決各子問題。
合併：將各子問題的解合併為原問題的解。