Symmetric Tree

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

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

  1.     1
  2.    / \
  3.   2   2
  4.  / \ / \
  5. 3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

  1.     1
  2.    / \
  3.   2   2
  4.    \   \
  5.    3    3

Note:

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

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  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.     }
  15.     return isSymmetric(root.left, root.right);
  16.   }
  18.   boolean isSymmetric(TreeNode left, TreeNode right) {
  19.     if (left == null && right == null) return true;
  20.     if (left == null || right == null) return false;
  21.     if (left.val != right.val) return false;
  22.     return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
  23.   }
  24. }