5 ms JAVA easy-to-understand traversal solution


  • 0
    Z
     public boolean isValidBST(TreeNode root) {
            if(root==null)return true;
            if(root.left==null&&root.right!=null)return rightValid(root.val,root.right)&&isValidBST(root.right);
            if(root.left!=null&&root.right==null)return leftValid(root.val,root.left)&&isValidBST(root.left);
            if(root.left!=null&&root.right!=null)return rightValid(root.val,root.right)&&leftValid(root.val,root.left)&&isValidBST(root.left)&&isValidBST(root.right);
            return true;
        }
        
        public boolean leftValid(int referval, TreeNode root){
            if(root==null)return true;
            return (root.val<referval)&&leftValid(referval,root.left)&&leftValid(referval,root.right);
        }
        public boolean rightValid(int referval, TreeNode root){
            if(root==null)return true;
            return (root.val>referval)&&rightValid(referval,root.left)&&rightValid(referval,root.right);
        }
    

  • 1
    J

    Could you explain the time complexity please? Is it O(n*2^n) ?


  • 0
    Z

    Yes, I think so. It's a slow algorithm compared to the iterative one. I would be more than happy if you can accelerate it.


  • 0
    L

    your solution is too slow!


Log in to reply
 

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