JAVA Solution, beats 90%


  • 10
    G

    Always check the depth of the right sub tree. If the depth equals that of left sub tree, the nodes count of left sub tree would be clear.
    The depth of left sub tree will always be known by node's father, so this value can be passed recursively.

    public class Solution {

    public int countNodes(TreeNode root) {
        TreeNode temp = root;
        int height = -1;
        while(temp != null) {
            height++;
            temp = temp.left;
        }
        return count(root, height);
    }
    
    public int count(TreeNode node, int depth) {
        if(node == null) {
            return 0;
        }
        TreeNode temp = node.right;
        int rightHeight = 0;
        while(temp != null) {
            rightHeight++;
            temp = temp.left;
        }
        if(rightHeight == depth) {
            return (1 << depth) + count(node.right, rightHeight - 1);
        } else {
            return (1 << (depth - 1)) + count(node.left, depth - 1);
        }
    }
    

    }


  • 0
    D
    This post is deleted!

  • 0
    D

    Could you please explain the intuition of "return (1 << (depth - 1)) + count(node.left, depth - 1);" when rightHeight != depth?

    Is 1<<(depth - 1) = number of nodes of left subtree + current root node? If it's the case, then why adding count(node.left, depth - 1); can give us what we need here?

    Thank you!


Log in to reply
 

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