HappyLeetcode43:Symmetric Tree

浏览数：28 / 时间：2015年06月11日

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

这道题目可以用迭代的方式做，也可以用递归的方式做。遇见和树相关的题目，第一反应是递归，所以我的解法是递归。

代码奉上：

class Solution {
 public:
     bool IsSymmetric(TreeNode *node1, TreeNode *node2)
     {
         if (node1 == NULL&&node2 == NULL)
             return true;
         if (node1 == NULL||node2 == NULL)
             return false;
         bool result1, result2;
         if (node1->val != node2->val)
             return false;
         else
         {
             result1 = IsSymmetric(node1->left, node2->right);
             result2 = IsSymmetric(node1->right, node2->left);
         }
         return result1&&result2;
     }
     bool isSymmetric(TreeNode *root) {
         if (root == NULL || root->left == NULL&&root->right == NULL)
             return true;
         bool result = IsSymmetric(root->left, root->right);
         return result;
     }
 };

看了相关人的解法，有的人直接用迭代的方式解出来了，感觉很受启发

/**
 * 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) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(root == NULL)return true;
        queue<TreeNode*> qleft, qright;
        if(root->left)qleft.push(root->left);
        if(root->right)qright.push(root->right);
        while(qleft.empty() == false && qright.empty() == false)
        {
            TreeNode *ql = qleft.front();
            TreeNode *qr = qright.front();
            qleft.pop();  qright.pop();
            if(ql->val == qr->val)
            {
                if(ql->left && qr->right)
                {
                    qleft.push(ql->left);
                    qright.push(qr->right);
                }
                else if(ql->left || qr->right)
                    return false;
                if(qr->left && ql->right)
                {
                    qleft.push(qr->left);
                    qright.push(ql->right);
                }
                else if(qr->left || ql->right)
                    return false;
            }
            else return false;
        }
        if(qleft.empty() && qright.empty())
            return true;
        else return false;
    }
};