人森很精彩，所以要把所有事情都記起來=ˇ=

這題算簡單吧

判斷一棵二元樹是否為對稱的，比如說：

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

如果是這樣就不算對稱：

    1
   / \
  2   2
   \   \
   3    3

Sol:

第一個想到的方法是用level order的一種變形方式來找

左子樹每一層從左到右的數值都會對應到右子樹每一層從右到左的數值，利用這點來判斷是否為對稱

大概可以這樣寫：

bool isSymmetric(TreeNode* root) {
        if (root == NULL || (root->left == NULL && root->right == NULL))
            return true;
    
        queue<TreeNode*> qRight;
        qRight.push(root->right);
        
        queue<TreeNode*> qLeft;
        qLeft.push(root->left);
        
        while(!qRight.empty() && !qLeft.empty())
        {
            queue<TreeNode*> qRightTmp;
            queue<TreeNode*> qLeftTmp;
            
            while (!qRight.empty() && !qLeft.empty())
            {
                TreeNode* rCur = qRight.front();
                TreeNode* lCur = qLeft.front();
                
                if (rCur != NULL && lCur != NULL)
                {
                    if (rCur->val != lCur->val)
                        return false;
                }
                else if (rCur != NULL || lCur != NULL)
                {
                    return false;
                }
                
                if (rCur && lCur)
                {
                    qRightTmp.push(rCur->left);  // 對右子樹來說，先放left進去，表示從左到右
                    qRightTmp.push(rCur->right);
                    
                    qLeftTmp.push(lCur->right);  // 對左子樹來說，先放right進去，表示從右到左
                    qLeftTmp.push(lCur->left);
                }
                
                qRight.pop();
                qLeft.pop();
            }
            
            qRight = qRightTmp;
            qLeft = qLeftTmp;
        }
        
        return true;
    }

嗯... 當然有很多地方可以優化啦，不過觀念對就行了

還有另一種是用遞迴的方式

大概的概念就是左節點的left會等於右節點的right，左節點的right會等於右節點的left

利用這點去遞迴判斷：

class Solution {
public:
    bool helper(TreeNode* left, TreeNode* right)
    {
        if (left == nullptr && right == nullptr)
            return true;
        
        if (left == nullptr || right == nullptr)
            return false;
        
        if (left->val == right->val)
        {
            return helper(left->left, right->right) 
                   && helper(left->right, right->left);
        }
        
        return false;
    }
    
    bool isSymmetric(TreeNode* root) {
        if (root == NULL || (root->left == NULL && root->right == NULL))
            return true;
        
        return helper(root->left, root->right);
    }
};

好吧，其實我覺得第一種比較好理解，第二種想一想我還會搞混...

執行速度和記憶體使用量也都是第一種比較好

那麼這題就這樣了，來去睡覺~