[C++]LeetCode: 36 Symmetric Tree

題目：

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

For example, this binary tree is symmetric:

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

But the following is not:

1
   / \
  2   2
   \   \
   3    3
      

Note:

Bonus points if you could solve it both recursively and iteratively.

判斷一棵樹是否中軸對稱.

Answer 1: iteratively 非遞歸方法。 樹的先序周遊

思路：構造兩個隊列，分别存儲跟結點的左右子樹。然後每次對稱的判斷值是否相等。

Attention:

1.  無論根結點的左右結點是否存在都要push進隊列(不存在push(NULL))，這樣才能在循環裡判斷。

    LTreeQ.push(root->left);

    RTreeQ.push(root->right);

2.  按照對稱的結構存儲結點. 隊列判斷值相等時才是正确的。

        LTreeQ.push(left->left);

        LTreeQ.push(left->right);

        RTreeQ.push(right->right);

        RTreeQ.push(right->left);

AC Code:

/**
 * Definition for binary tree
 * 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;
    
    queue<TreeNode*> LTreeQ, RTreeQ;
    /*
    if(root->left) LTreeQ.push(root->left);
    if(root->right) RTreeQ.push(root->right);
    */
    //無論根結點的左右結點是否存在都要push進隊列(不存在push(NULL))，這樣才能在循環裡判斷。
    LTreeQ.push(root->left);
    RTreeQ.push(root->right);
    while(!LTreeQ.empty() && !RTreeQ.empty())
    {
        TreeNode* left = LTreeQ.front();
        LTreeQ.pop();
        TreeNode* right = RTreeQ.front();
        RTreeQ.pop();
        
        if(left == NULL && right == NULL) continue;
        //上面判斷了全NULL情況，這句表示其中一個為NULL
        if(left == NULL || right == NULL) return false;
        
        if(left->val != right->val) return false;
        
        //按照對稱的結構存儲結點
        LTreeQ.push(left->left);
        LTreeQ.push(left->right);
        RTreeQ.push(right->right);
        RTreeQ.push(right->left);
    }
  
    return true;      
    }
};
           

Answer 2: recursively  遞歸方法

思路：遞歸的判斷下一層是否對稱。構造遞歸函數時傳入左結點和右結點兩個參數。

Attention: 注意要按照對稱的判斷值傳入結點。

AC Code:

/**
 * Definition for binary tree
 * 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) return true;
        return isSymmetric(root->left, root->right);
    }
    
    bool isSymmetric(TreeNode* lt, TreeNode* rt){
        if(!lt && !rt) return true;
        if(!lt || !rt || lt->val != rt->val) return false;
        
        return isSymmetric(lt->left, rt->right) && isSymmetric(lt->right, rt->left);
    }
};