Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：判断一棵二叉树是否是自己的镜像。做法是做个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:
12
13 bool leaf(TreeNode* root)
14 {
15 if (root->left==NULL&&root->right==NULL) return true;
16 return false;
17 }
18 bool mirror(TreeNode* rt1,TreeNode* rt2)
19 {
20
21 if (rt1==NULL&&rt2==NULL) return true;
22 if (rt1==NULL||rt2==NULL) return false;
23 printf("%d %d\n",rt1->val,rt2->val);
24 if (leaf(rt1)&&leaf(rt2)&&rt1->val==rt2->val) return true;
25 if (leaf(rt1)||leaf(rt2)) return false; //包含了其中一个是叶子，或者两个都是叶子但是值不相等的情况。
26 if (rt1->val!=rt2->val) return false; //不是叶子，但是值不相等，没必要继续了。
27 bool res = true;
28 res = mirror(rt1->left,rt2->right);
29 if (!res) return false;
30 res = mirror(rt2->left,rt1->right);
31 if (!res) return false;
32 return true;
33 }
34 bool isSymmetric(TreeNode* root) {
35 if (root==NULL) return true;
36 return mirror(root,root);
37
38 }
39};