[Leetcode] 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:

But the following is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

Solution 1:　　 recursive

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public boolean isSymmetric(TreeNode root) {
12         if (root == null)
13             return true;
14         return mySymmetric(root.left,root.right);
15         
16     }
17 
18     private boolean mySymmetric(TreeNode left, TreeNode right) {
19         // TODO Auto-generated method stub
20         if(left==null&&right==null)
21             return true;
22         if(left==null||right==null)
23             return false;
24         return (left.val==right.val)&&mySymmetric(left.right, right.left)&&mySymmetric(left.left, right.right);
25     }
26 }

Solution 2:　　iterative

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public boolean isSymmetric(TreeNode root) {
12         //iterative way
13         if(root==null)
14             return true;
15         Stack<TreeNode> sl=new Stack<TreeNode>();
16         Stack<TreeNode> sr=new Stack<TreeNode>();
17         sl.add(root.left);
18         sr.add(root.right);
19         while(!sl.isEmpty()&&!sr.isEmpty()){
20             TreeNode n1=sl.pop();
21             TreeNode n2=sr.pop();
22             if(n1==null&&n2==null)
23                 continue;
24             if(n1==null||n2==null)
25                 return false;
26             if(n1.val!=n2.val)
27                 return false;
28             sl.push(n1.left);
29             sl.push(n1.right);
30             sr.push(n2.right);
31             sr.push(n2.left);
32         }
33         return true;
34     }
35 }