10-line solution with recursion in Java


  • 2
    public class Solution {
        public boolean isSymmetric(TreeNode root) {
            return check (root, root);
        }
        public boolean check(TreeNode p , TreeNode q){
            if (p==null&&q==null) return true;
            if (p==null^q==null || p.val != q.val) return false;
            return check(p.left,q.right)&&check(p.right,q.left);
        }
    }

  • 0
    G

    Mine was very similar, however it should be noted that your solution checks the entire tree twice due to the check(root, root) call. This recurses on root.left, root.right in the first check, then root.right, root.left on the second check which is redundant and results in an extra traversal of the tree. The following eliminates the redundant check.

    bool isSymmetric(TreeNode *root) {
        if (root == NULL) return true;
        return isSymmetric(root->left, root->right);
    }
    
    bool isSymmetric(TreeNode *left, TreeNode *right) {
        if (left == NULL && right == NULL) return true;
        if (left == NULL || right == NULL) return false;
        return left->val == right->val && isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
    }

  • 0
    P
    public boolean isSymmetric(TreeNode root) {
    	return isSymmetric(root, root);
    }
    
    private boolean isSymmetric(TreeNode node1, TreeNode node2) {
    	if (node1 == null || node2 == null) return node1 == null && node2 == null;
    	return node1.val == node2.val&&isSymmetric(node1.left, node2.right) && isSymmetric(node1.right, node2.left);
    }
    

Log in to reply
 

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