LeetCode: Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

用递归的方法很好做。先比较对应的两个节点数值是否相同,如果相同就看第一个节点的左子和第二个节点的右子是否对称,以及第一个节点的右子和第二个节点的左子。

LeetCode: Symmetric Tree
 1 public static boolean isSymmetric(TreeNode root) {
 2         if (root == null) return true;
 3         else return check(root.left, root.right);
 4     }
 5     
 6     public static boolean check(TreeNode left, TreeNode right) {
 7         if (left == null && right == null) return true;
 8         else if (left != null && right != null) {
 9             if (left.val == right.val) {
10                 return check(left.left, right.right) && check(left.right, right.left);
11             }
12             else return false;
13         }
14         else return false;
15     }
LeetCode: Symmetric Tree

如果用iterative的方法,还真是一时没想到。一想也不能是dfs,估计就是bfs。但是用bfs怎么能比较同一层的元素是否对称。。。因为我想的是bfs都放到一个list中,要比较是否对称需要把元素都倒出来。然后还要把下一层的放进去。。。就不知道咋做了。。。。

后来网上学习了一下。可以用两个queue。一个queue bfs左子树,一个queue bfs右子树。bfs的顺序不同,一个先左后右,一个先右后左。这样对比每个出队的元素,也不用记录哪层是哪层之类的。。

LeetCode: Symmetric Tree
 1 class Solution {
 2 public:
 3     bool isSymmetric(TreeNode *root) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         if(root==NULL) return true;
 7         queue<TreeNode*> q1;
 8         queue<TreeNode*> q2;
 9         
10         q1.push(root->left);
11         q2.push(root->right);
12         
13         while(!q1.empty()&&!q2.empty())
14         {
15             TreeNode *t1=q1.front();
16             TreeNode *t2=q2.front();
17             q1.pop();
18             q2.pop();
19             
20             if((t1!=NULL&&t2==NULL)||(t1==NULL&&t2!=NULL)) 
21             return false;
22             
23             if(t1!=NULL&&t2!=NULL)
24             {
25                 if(t1->val!=t2->val) 
26                 return false;
27                 
28                 q1.push(t1->left);
29                 q1.push(t1->right);
30                 q2.push(t2->right);
31                 q2.push(t2->left);
32             }
33         }
34         return true;
35         
36     }
37 };
LeetCode: Symmetric Tree

LeetCode: Symmetric Tree

上一篇:topcoder srm 570 div1


下一篇:PHP数据库备份与恢复