Posted on 2014-01-11 02:33
Uriel 阅读(100)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
判断一棵二叉树是否左右对称,设两个指针,一个左-根-右遍历,另一个右-根-左遍历,存遍历结果,一样的话就是对称的,注意,一个指针为NULL另一个不为NULL的情况!
1 /**
2 * Definition for binary tree
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 queue<TreeNode *> que;
13 vector<int> lst;
14 bool ok;
15
16 void jge(TreeNode *r1, TreeNode *r2) {
17 if(r1->val != r2->val) ok = false;
18 if(r1->left == NULL && r2->right != NULL) {
19 ok = false;
20 }
21 else if(r1->left != NULL && r2->right == NULL) {
22 ok = false;
23 }
24 else if(r1->left != NULL && r2->right != NULL) {
25 jge(r1->left, r2->right);
26 }
27 if(r1->val != r2->val) ok = false;
28 if(r1->right == NULL && r2->left != NULL) {
29 ok = false;
30 }
31 else if(r1->right != NULL && r2->left == NULL) {
32 ok = false;
33 }
34 else if(r1->right != NULL && r2->left != NULL) {
35 jge(r1->right, r2->left);
36 }
37 }
38
39 bool isSymmetric(TreeNode *root) {
40 ok = true;
41 if(root == NULL) return ok;
42 else
43 jge(root, root);
44 return ok;
45 }
46 };