67ms Simple Java Solution Beats 91%


  • 0

    The idea is the same as Stefan's solution. The only improvement is to not discard previous calculated heights, too eliminate duplicate calculations.
    ...

    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        
        return countNodes(root, heightR(root.right));
    }
    
    // Recursively solve the problem
    // rHeightR is the result of heightR(root.right), which is calculated already
    // in previous call, as heightR(root) - 1 = heightR(root.right)
    public int countNodes(TreeNode root, int rHeightR) {
        if (root == null) return 0;
        
        int lHeightR = heightR(root.left);
        if (lHeightR == rHeightR) { // Right is full
            return countNodes(root.left, lHeightR-1) + (1 << rHeightR);
        } else {
            return countNodes(root.right, rHeightR-1) + (1 << lHeightR);
        }
    }
    
    // The length of the path from the Root to its right most leaf    
    private int heightR(TreeNode root) {
        if (root == null) return 0;
        
        return 1 + heightR(root.right);
    }
    

    ...


Log in to reply
 

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