101

這題要計算一棵樹是不是對稱的，其中對稱的定義是對樹的中間對稱。另外如果寫出recursive和iterative兩種版本的話，可以額外加分。

Recursive的解法

直觀上的想法，會想要從root出發，去比較第二層left child跟right child是不是一樣，如果一樣再往下比，一開始想會覺得如果再往第三層比，好像很麻煩，因為要比最左邊和最右邊的孫子、還有靠近中間的兩個孫子。這時我才突然意識到，原來我最直觀的思維還是以root為核心，然後想要從root出發直接把演算法寫完。可是tree這種資料結構有趣的地方在於，我們可以把某個子節點當成root，這也是為什麼tree相關的問題很容易用recursive的解法來做，因為問題的形式相同，只是範圍不斷縮小。聯想到樹的問題的話就可以寫出:

問題的形式相同:一樣都是樹 範圍不斷縮小:因為不斷將子樹當成整個樹，所以範圍不斷縮小

接下來就先把程式的行為想清楚:

1. 如果root是NULL，return true
2. 傳入left child跟right child給一個recursive function來判斷這兩棵子樹是否對稱
3. 如果傳入的left child和right child有一個是NULL，那就看是兩個都是NULL(回傳true)，或是只有一個是NULL(回傳false)
4. 如果都不是NULL，就比較一下val，如果不一樣就回傳false
5. 如果val都一樣，就比較(left->right, right->left)(內層的孫子)跟(left->left, right->right)(外層的孫子)，只要有false就回傳false

然後就可以實作出recursive版本的code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)
            return true;

        return symmetricChild(root->left, root->right);
    }

    bool symmetricChild(TreeNode* left, TreeNode* right)
    {
        if(left == NULL || right == NULL)
        {
            if(left == NULL && right == NULL)
                return true;
            else
                return false;
        }

        if(left->val != right->val)
            return false;

        if(!symmetricChild(left->right, right->left) || !symmetricChild(left->left, right->right))
            return false;

        return true;
    }
};

寫到這邊，突然有點想要再多想一下演算法的本質。在解這個問題的時候，我才突然意識到recursive這種解法的適用之處。再延伸思考一下，其實要寫出好的演算法，就是要先看出問題的本質，例如我們先看到了這個問題的本質是一個不斷往下層去比對，直到全部比對完的問題。(而且不能不比完，只要有一個node沒有比到，我們就不能拍胸脯保證說這棵樹symmetric。)

看到這個本質之後，我們就不可能會想用dynamic programming的演算法來解這個問題，因為這個問題的本質，我們根本不能用dynamic programming來解。但我們之所以不會想用dynamic programming來解這個問題，前提也是我們已經了解dynamic programming的本質，我們知道它可以用來解決什麼問題。

所以在練習這種演算法題目的過程中，我們其實是在訓練自己

1. 看清楚問題本質的能力
2. 看清楚幾種重要類型演算法本質的能力(例如recursive, iterative, greedy, DP等等)

這兩個能力不就是我們身為工程師本來就要具備的能力嗎? 所以刷題確實是有其意義，這些題目是一個個很小的練習場，讓我們可以鍛鍊這兩項能力，然後從easy->medium->hard一步步更加強。

Iterative的解法

目前我們對問題的本質有一定的了解了，如果想用iterative的解法，那就要看清楚iterative演算法的本質。(其實是為了加分XD)

講到iterative演算法，最直覺想到的就是for迴圈了。for迴圈最簡單的範例大概就是印出1~10的正整數:

for(int i=1; i<=10; i++)
    cout << i << endl;

聯想到這題，就會覺得應該是要把左子樹跟右子樹的val依序塞進各自的vector裡，然後只要比較這兩個vector是否一樣即可。可想而知，這邊的依序就是重點了，因為我們是要判斷兩邊是否對稱，所以左子樹應該是要從每一層的最左邊開始存val，右子樹則是要從每一層的最右邊開始存val。

將兩邊子樹的所有val都塞進各自的vector之後，就再用一個for迴圈比較兩邊的element是否都一樣就好。關於怎麼把兩邊的val都塞進vector，就讓人聯想到102題，這邊就再利用102題的程式碼來實作一下iterative版本。

Java recursive版本：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        /*
        Concept:
        root的左子樹和右子數如果對稱，那整棵樹就是對稱的。
        如何判斷右子樹和左子樹對稱？
        -> 右子樹的左子樹和左子樹的右子樹相同; 右子樹的右子樹和左子樹的左子樹相同
        */
        if(root==null)
            return true;
        return isSymmetric(root.left,root.right);
    }

    boolean isSymmetric(TreeNode p, TreeNode q){
        if(p==null && q==null){
            return true;
        }else if(p==null || q==null){
            return false;
        }else{
            if(p.val == q.val){
                return isSymmetric(p.right, q.left) && isSymmetric(p.left,q.right);
            }
            return false;
        }

    }
}