Recursive and non-recursive solutions in Java


  • 210
    L

    Recursive--400ms:

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

    Non-recursive(use Stack)--460ms:

    public boolean isSymmetric(TreeNode root) {
        if(root==null)  return true;
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode left, right;
        if(root.left!=null){
            if(root.right==null) return false;
            stack.push(root.left);
            stack.push(root.right);
        }
        else if(root.right!=null){
            return false;
        }
            
        while(!stack.empty()){
            if(stack.size()%2!=0)   return false;
            right = stack.pop();
            left = stack.pop();
            if(right.val!=left.val) return false;
            
            if(left.left!=null){
                if(right.right==null)   return false;
                stack.push(left.left);
                stack.push(right.right);
            }
            else if(right.right!=null){
                return false;
            }
                
            if(left.right!=null){
                if(right.left==null)   return false;
                stack.push(left.right);
                stack.push(right.left);
            }
            else if(right.left!=null){
                return false;
            }
        }
        
        return true;
    }

  • 0
    D

    Nice solution. Thanks for sharing.


  • 0
    Y

    That really helps!


  • 65
    E
       if(left==null || right==null)
        return left==right;
    

    nice one!


  • 0
    S

    Agree! Agree! Agree!


  • 20
    D

    My recursion solution java : 243 ms

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

  • 0
    S
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    M

    Smart solution, thanks a lot!


  • 0
    W

    I don't think this line can pass any code review in any company


  • 1
    Z

    How did you find out the execution time?


  • 0
    Z

    why ? I think it is a good one


  • 0
    H

    indeed, poor readability


  • 1
    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            if(!root)   return true;
            return help(root->left, root->right);
        }
        bool help(TreeNode* left, TreeNode* right){
            if(left==NULL && right==NULL)   return true;
            if(left==NULL || right==NULL)   return false;
            if(left->val!=right->val)    return false;
            else{
                /***   the key point is the make sure the sub-tree pair relationship  ***/
                return help(left->left, right->right) && help(left->right, right->left);
            }
        }
    };

  • 0
    N

    Thanks for sharing, very easy to understand!


  • 13

    Same code for Iterative, but just reducing the size :)

    public boolean isSymmetric(TreeNode root) {
        if(root==null)  return true;
    
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode left, right;
        if(!process(root.left, root.right, stack)) return false;
    
        while(!stack.empty()){
            if(stack.size()%2!=0)   return false;
            right = stack.pop();
            left = stack.pop();
            if(right.val!=left.val) return false;
            if(!process(left.left, right.right, stack)) return false;
            if(!process(left.right, right.left, stack)) return false;
        }
        return true;
    }
    
    public boolean process(TreeNode a, TreeNode b, Stack<TreeNode> s) {
        if(a != null) {
            if(b == null) return false;
            s.push(a);
            s.push(b);
        }else if(b != null) return false;
        return true;
    }

  • 1
    J

    nice.thank you.why my commit is 1ms.


  • 1
    J

    just code clearly.nothing


  • 0
    S

    what's the time complexity for recursive solution? I think the average is O(logN) while the worst case is O(N). correct me if i am wrong.


  • 0
    N

    It is o(n) since it has to traverse whole tree.


Log in to reply
 

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