Recursive Java Solution With Explanation


  • 0
    M

    So as you have observed, the symmetry is like the mirror image. So if you draw a tree on paper and fold the paper from the middle or root, then the elements that overlap each other should be same. Since the tree with no element or only the root element will always be symmetrical, we need to check if the left and the right subtree are symmetrical or not. Thus the below recursive algorithm is used/

    1. if root is null, then return true
    2. Else call checkSymmetry(root.left, root.right)
    3. Inside checkSymmetry, do the following
      3a. Check if left == null && right == null --> return true
      3b. Check if (left! != null && right == null) || (left == null && right != null) --> return false;
      3c. Check if left.val == right.val && recurse()

    Now recurse on left.left, right.right and left.right, right.left

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.