leetcode Symmetric Tree

题目链接

symmetric-tree

题目描述(Description)

Symmertic 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:

But the following is not:

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

对称二叉树

给一个二叉树，检查它的镜像数是否和原来的树一样（也就是说，关于原树的中心对称）

例如：第一个二叉树是对称的，第二个树不对称。

注意：

如果分别用递归和迭代解答会有奖励。

分析(Analysis)

递归解法：

• 先判断根节点是否为空或者是否只有一个根节点，若空，返回True。

• 另外写一个函数，判断结点的左右子树是否对称。要判断对称，则只要判断left结点的左子树与right结点的左子树是否相同，left结点的右子树与right结点的左子树是否相同。

• 两树不相同的条件：左子为空右子不为空、右子为空左子不为空、左右子都不为空但数值不同。

代码(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 isMir(TreeNode *left,TreeNode *right){
        if(!left&&!right)
            return true;
        if((!left&&right)||(left&&!right)||(left->val!=right->val))//两树不相同的条件
            return false;
        return isMir(left->left,right->right)&&isMir(left->right,right->left);
    }
    bool isSymmetric(TreeNode *root) {
        if(!root)//空结点
            return true;
        if(!root->left&&!root->right)//只有一个根节点
            return true;
        else
            return isMir(root->left,root->right);
    }
};