2015年10月2日星期五

Leetcode 101 Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
    1
   / \
  2   2
 / \ / \
3  4 4  3
But the following is not:
    1
   / \
  2   2
   \   \
   3    3
Note:
Bonus points if you could solve it both recursively and iteratively.
Solution 1: recursive
 public class Solution {  
   public boolean isSymmetric(TreeNode root) {  
     return dfs(root, root);  
   }  
   private boolean dfs(TreeNode x, TreeNode y) {  
     if (x==null && y==null) return true;  
     if (x==null || y==null) return false;  
     if (x.val!=y.val) return false;  
     return dfs(x.left, y.right) && dfs(x.right, y.left);  
   }  
 }  

Solution 2: iterative
 public class Solution {  
   public boolean isSymmetric(TreeNode root) {  
     Deque<TreeNode> s1=new LinkedList<>();  
     Deque<TreeNode> s2=new LinkedList<>();  
     TreeNode x=root, y=root;  
     while (x!=null || y!=null || !s1.isEmpty()) {//s1,s2 always pop.push same time  
       if (x!=null || y!=null) {  
         if (x==null || y==null) return false;  
         if (x.val!=y.val) return false;  
         s1.push(x);  
         s2.push(y);  
         x=x.left;  
         y=y.right;  
       }  
       else {  
         x=s1.pop();  
         y=s2.pop();  
         x=x.right;  
         y=y.left;  
       }  
     }  
     return true;  
   }  
 }  

没有评论:

发表评论