1.3 Symmetric Binary Tree

Assumption: given root is not null

Input: TreeNode left, TreeNode right, no need to check the root

Output: boolean

Solution:

The subproblem is whether two corresponding nodes are symmetric. Check if left.left == right.right && left.right == right.left

Case 1: left == null && right == null, return true

Case 2: one of them is null, return false

Case 3: left.key != right.key, return false

public boolean isSymmetric(TreeNode left, TreeNode right) {
  if (left == null && right == null) { return true; }
  else if (left == null || right == null) { return false; }
  else if (left.key != right.key) { return false; }
  return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
}