Accepted Easy Understand Java Solution


  • 113
    M

    public class Solution {

    public int countNodes(TreeNode root) {
    
        int leftDepth = leftDepth(root);
    	int rightDepth = rightDepth(root);
    
    	if (leftDepth == rightDepth)
    		return (1 << leftDepth) - 1;
    	else
    		return 1+countNodes(root.left) + countNodes(root.right);
    
    }
    
    private int rightDepth(TreeNode root) {
    	// TODO Auto-generated method stub
    	int dep = 0;
    	while (root != null) {
    		root = root.right;
    		dep++;
    	}
    	return dep;
    }
    
    private int leftDepth(TreeNode root) {
    	// TODO Auto-generated method stub
    	int dep = 0;
    	while (root != null) {
    		root = root.left;
    		dep++;
    	}
    	return dep;
    }
    

    }


  • 0
    M
    This post is deleted!

  • -5
    E

    LOL SO BAD. NEW LEVEL OF BADNESS.


  • -5
    E

    DO YOU EVEN ALGORITHM BRO


  • -5
    E

    YOU WROTE TWO HELPER METHODS THAT DO THE EXACT SAME THING


  • -6
    E

    YOU DONT EVEN NEED A HELPER METHOD. JUST CALL THE ORIGINAL METHOD ON ROOT.LEFT AND ROOT.RIGHT https://leetcode.com/discuss/59880/clean-solution-stackoverflow-plserino-feedback-welcomed
    HAHAHAHAHAAHAHAHA LOLOLOLOLOLOLOLOL XDDDDDDDDDDDDDDDDD.


  • 1
    M

    Your solution is used to count tree nodes for any tree. But this is a complete tree, you can use its property to speed up the algorithm~


  • 1
    M

    My solution only count when the root is not a perfect tree root, which saves half time each iteration, so it's log(n) solution.


  • 0
    P

    What a brilliant solution!


  • 1
    B

    Very clever solution. To avoid the redundancy of the leftDepth and rightDepth methods you could create an enum class:
    public Enum Direction{
    LEFT, RIGHT
    }
    and you can make a getDepth method take direction as an argument. The method would look
    private int leftDepth(TreeNode root, Direction dir) {
    int dep = 0;
    while (root != null) {
    if (dir == Direction.LEFT){
    root = root.left;
    } else {
    root = root.right
    }
    dep++;
    }
    return dep;
    }


  • 0
    M

    Thank you very much. Very nice idea. I need to get familiar with enmu class.


  • 0
    X

    Clean and Clear. Great Solution.


  • 0
    Y

    I got very confused... what does "1 << leftDepth) - 1" mean? and why does that work? I think it should be exponential. like Math.pow(2, leftDepth) - 1. Could you explain it? Thanks!


  • 2
    M

    << and >> are bit manipulate operators, it means to move the 32 bit integer to left or to right, which essentially does what pow(2,n) does. When the exponential base is 2, use bit moving operations are fast.


  • -1
    N

    This solution is very easy to understand!


  • 0
    Y

    The solution is giving TLE now.


  • 0
    M

    Leetcode OJ has been kind of unstable. If you got a TLE with this code, it must be a wrong time you were trying.


  • 0
    J

    kind of slow


  • 2
    H

    I think the time complexity should be O(log(n)^2)


  • 1
    S

    This is an awesome solution! Super clear and easy to follow! Upvote!
    My understanding of your code:
    Two cases:

    1. when it's a full binary tree, will be the easiest case: just return (1 << leftHeight) -1

    2. when it's not full binary tree we'll calculate its left and right subtree nodes recursively and then plus one (root node).

    One more comment: I'd like to add one more line:

    if(root == null) return 0;
    

    at the beginning of your countNodes(TreeNode root) function, it at least helps me understand it better, basically, that line serves as the base case when the countNodes() function exits. Otherwise, it's not super clear to me when countNodes() reaches null, how it's going to return.

    Please advise.


Log in to reply
 

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