Concise solution of 13 lines.


  • 1
    S
        public int countNodes(TreeNode root) {
        if(root == null) return 0;
        int left =1+ height(root.left);
        int right=1+ height(root.right);
        if(left == right)
            return 1+ ((1 << left-1) - 1) + countNodes(root.right);
        else
            return 1 + ((1 << right-1) - 1) + countNodes(root.left);
    }
    private int height(TreeNode root){
        if(root == null) return 0;
        return 1 + height(root.left);
    }
    

    The solution finds the height difference between left most node and leftmost node of right child and then does the math to add the nodes.


Log in to reply
 

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