leetcode 101. Symmetric Tree Add to List（二叉树，判断镜像）

2017-02-24 · 1 min read

题目链接

题意：判断一棵二叉树是否是自己的镜像。做法是做个copy，相当于两棵树做比较。注意逻辑不要漏掉就好

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8 * };
 9 */
10class Solution {
11public:

1    bool leaf(TreeNode* root)
2    {
3        if (root->left==NULL&&root->right==NULL) return true;
4        return false;
5    }   
6    bool mirror(TreeNode* rt1,TreeNode* rt2)
7    {

 1        if (rt1==NULL&&rt2==NULL) return true;
 2        if (rt1==NULL||rt2==NULL) return false;
 3             printf("%d %d\n",rt1->val,rt2->val);
 4        if (leaf(rt1)&&leaf(rt2)&&rt1->val==rt2->val) return true;
 5        if (leaf(rt1)||leaf(rt2)) return false; //包含了其中一个是叶子，或者两个都是叶子但是值不相等的情况。
 6        if (rt1->val!=rt2->val) return false; //不是叶子，但是值不相等，没必要继续了。
 7        bool res = true;        
 8         res = mirror(rt1->left,rt2->right);
 9        if (!res) return false;
10          res = mirror(rt2->left,rt1->right);
11        if (!res) return false;
12        return true;
13    }
14    bool isSymmetric(TreeNode* root) {
15        if (root==NULL) return true;
16        return mirror(root,root);

    }
};