Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
判断一棵二叉树是不是左右对称的,简单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)

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理