刷題日記(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)
解題方式
- 分治法(使用遞歸)
遞迴的三種情況
- 相比的兩個點皆為null, 則回傳 True

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

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

(main function)
- 如果傳進來的node為null, 則回傳true
- 接著不為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為分界線,然後判斷左子樹和右子樹是不是相等就好(因此其實應該也可以用 BFS解,之後有空再補)


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

*Divide and conquer中文翻作分治法,概念如字面上的意義,將問題先切分成小問題後再解決,再將結果合併求出原始問題的答案。
以下摘錄自Wiki
分解:將原問題分解為若干個規模較小,相對獨立,與原問題形式相同的子問題。
解決:若子問題規模較小且易於解決時,則直接解。否則,遞歸地解決各子問題。
合併:將各子問題的解合併為原問題的解。