Symmetric Tree

Problem

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

Examples

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

    1
   / \
  2   2
   \   \
    3    3

Input: root = [1,2,2,null,3,null,3]
Output: false

Solution

Method 1 - Recursion

This problem can be solve by using a simple recursion. The key is finding the conditions that return false, such as value is not equal, only one node(left or right) has value.

public boolean isSymmetric(TreeNode root) {
    if (root == null) {
	    return true;
	}
    return isSymmetric(root.left, root.right);
}

public boolean isSymmetric(TreeNode l, TreeNode r) {
    if (l == null && r == null) {
        return true;
    } else if (r == null || l == null) {
        return false;
    }

    return l.val == r.val && 
    isSymmetric(l.left, r.right) && 
    isSymmetric(l.right, r.left);
}