Symmetric Tree

Problem:

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

Solution:

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:      else  
15:       return isSym(root.left,root.right);  
16:    }  
17:    public boolean isSym(TreeNode left, TreeNode right){  
18:      if(left==null) return right==null;  
19:      if(right==null) return left==null;  
20:      if(left.val!=right.val) return false;  
21:      if(!isSym(left.right,right.left))  
22:       return false;  
23:      if(!isSym(left.left,right.right))  
24:       return false;  
25:      return true;  
26:    }  
27:  }  

Discussion:

Recursive solution. If a tree is symmetric, it satisfies 3 conditions:
1. left node value equals to right node value or they are all null.
2. The left node's left child is symmetric to right node's right child.
3. The left node's right child is symmetric to right node's left child.