1.9 Symmetric Tree

Description

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

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

Method

1. recursive check equality and the most left one with the most right one

2. iteratively stack

   Time and Space Complexity

   o(n) o(n)

   Code

   public class Solution { // recursive

    public boolean isSymmetric(TreeNode root) {
       if (root == null){
           return true;
       }
       return check(root.left, root.right);
     }
   
   public boolean check(TreeNode leftR, TreeNode rightR){
       if (leftR == null || rightR == null){
           return leftR == rightR;
       }
       if (leftR.val != rightR.val){
           return false;
       }
       return check(leftR.left, rightR.right) && check(leftR.right, rightR.left);
   

   }

}

// iteratively public boolean isSymmetric(TreeNode root) { if (root == null){ return true; } Stack s = new Stack(); if (root.left == null || root.right == null){ return root.left == root.right; } s.push(root.left); s.push(root.right); while (!s.isEmpty()){ if (s.size() % 2 != 0){ return false; } TreeNode right = s.pop(); TreeNode left = s.pop(); if (left.val != right.val){ return false; } if (left.left != null){ if (right.right == null){ return false; } s.push(left.left); s.push(right.right); } else if (right.right != null){ return false; } if (left.right != null){ if (right.left == null){ return false; } s.push(left.right); s.push(right.left); } else if (right.left != null){ return false; } } return true;

}