Elegant Java recursive solution 80ms


  • 0
    public int countNodes(TreeNode root) {
            if (root == null) {
                return 0;
            }
            
            int l = getHeight(root.left);
            int r = getHeight(root.right);
            int left = 0, right = 0;
           // Divide and conquer
            if (l > r) {
                right = (1 << r) - 1;
                left = countNodes(root.left);
            } else {
                left = (1 << l) - 1;
                right = countNodes(root.right);
            }
            // Combine results
            return left + right + 1;
        }
        
        public int getHeight(TreeNode root) {
            int count = 0;
            while (root != null) {
                count++;
                root = root.left;
            }
            return count;
        }
    

Log in to reply
 

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