Simple Java solution


  • 0
    S

    Got a timeout when using Math.pow(). Switching to bit shifts solved that.

    public class Solution {
    	public int countNodes(TreeNode root) {
    	    int h = height(root);
    	    int nodeCount = 0;
    	    
    	    while (root != null) {
    	        if (height(root.right) == h-1) {
    	            // Left is full. Add left plus root.
    	            nodeCount += (1 << h);  // 2**(h-1+1) - 1 + 1
    	            root = root.right;
    	        } else {
    	            // Right is full. Add right plus root.
    	            nodeCount += (1 << h-1);
    	            root = root.left;
    	        }
    	        h--;
    	    }
    	    return nodeCount;
    	}
    
    	public int height(TreeNode root) {
    	    if (root == null) return -1;
    	    return 1 + height(root.left);
    	}
    }

Log in to reply
 

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