判断一棵二叉树是不是左右对称的,简单DFS
C++版
1 //101
2 //Runtime: 16 ms (Beats 5.2%)
3
4 /**
5 * Definition for binary tree
6 * struct TreeNode {
7 * int val;
8 * TreeNode *left;
9 * TreeNode *right;
10 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11 * };
12 */
13 class Solution {
14 public:
15 queue<TreeNode *> que;
16 vector<int> lst;
17 bool ok;
18
19 void jge(TreeNode *r1, TreeNode *r2) {
20 if(r1->val != r2->val) ok = false;
21 if(r1->left == NULL && r2->right != NULL) {
22 ok = false;
23 }
24 else if(r1->left != NULL && r2->right == NULL) {
25 ok = false;
26 }
27 else if(r1->left != NULL && r2->right != NULL) {
28 jge(r1->left, r2->right);
29 }
30 if(r1->val != r2->val) ok = false;
31 if(r1->right == NULL && r2->left != NULL) {
32 ok = false;
33 }
34 else if(r1->right != NULL && r2->left == NULL) {
35 ok = false;
36 }
37 else if(r1->right != NULL && r2->left != NULL) {
38 jge(r1->right, r2->left);
39 }
40 }
41
42 bool isSymmetric(TreeNode *root) {
43 ok = true;
44 if(root == NULL) return ok;
45 else
46 jge(root, root);
47 return ok;
48 }
49 };
Python版
1 #101
2 #Runtime: 19 ms (Beats 77.4%)
3 #Memory: 13.6 MB (Beats 75.62%)
4
5
6 # Definition for a binary tree node.
7 # class TreeNode(object):
8 # def __init__(self, val=0, left=None, right=None):
9 # self.val = val
10 # self.left = left
11 # self.right = right
12 class Solution(object):
13 def isSymmetric(self, root):
14 """
15 :type root: TreeNode
16 :rtype: bool
17 """
18
19 def DFS(r1, r2):
20 if (not r1) and (not r2):
21 return True
22 if (not r1) or (not r2):
23 return False
24 return r1.val == r2.val and DFS(r1.left, r2.right) and DFS(r1.right, r2.left)
25
26 return DFS(root, root)