Why is my time algorithm exceeds the time limit?


  • 0
    Y

    public int countNodes(TreeNode root) {
    int num = 0;
    //boundary condition
    if(root == null) return 0;
    if(root.left == null && root.right == null) return 1;

        //get the depth of the tree
        TreeNode tmp = root;
        int depth = 0;
        while(tmp != null){
            depth ++;
            tmp = tmp.left;
        }
        
        int curDepth = depth;
        
        //binary search
        while(root != null){
            int leftDepth = curDepth - 1, rightDepth = 0;
            TreeNode right = root.right;
            //get the depth of the right child
            while(right != null){
                rightDepth ++;
                right = right.left;
            }
            
            if(leftDepth > rightDepth){
                num += 1 + Math.pow(2, leftDepth - 1) - 1;
                root = root.left;
            }
            else{
                num += 1 + Math.pow(2, leftDepth) - 1;
                root = root.right;
            }
            
            curDepth = leftDepth;
        }
        
        return num;
    }

Log in to reply
 

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