Posted on 2014-01-11 02:33
Uriel 閱讀(104)
評論(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 };