Simple java solution


  • 2
    H
    public int countNodes(TreeNode root) {
        if (root == null) {return 0;}
        if (root.left == null && root.right == null) {return 1;}
        if (root.right == null) {return 2;}
        int count = 0;
        if (helper(root.left) != helper(root.right)) {
            int temp = (2 << (helper(root.right) - 1));
            count += temp + countNodes(root.left);
        } else {
            int temp = (2 << (helper(root.left) - 1));
            count += temp + countNodes(root.right);
        }
        return count;
    }
    private int helper(TreeNode root) {
        if (root == null) {return 0;}
        int count = 1;
        while (root.left != null) {
            count++;
            root = root.left;
        }
        return count;
    }

  • 2

    Good solution, but I think you should bit manipulate "1" instead of "2". That will make the code shorter and more concise. Check this:

    public class Solution {
         int getLeftHeight(TreeNode root) {
            int height = 0;
            while (root != null) { 
                root = root.left;
                height++;
            }
            return height;
        }
        
        public int countNodes(TreeNode root) {
            if (root == null) return 0;
    
            int left_height = getLeftHeight(root.left);
            int right_height = getLeftHeight(root.right);
    
            if(left_height == right_height)
           		return (1 << left_height) + countNodes(root.right);
    
            return (1 << right_height) + countNodes(root.left);
        }
    }

  • 1
    J

    Thanks for your idea.

    public int countNodes(TreeNode root) {
        
        if (root == null) {
            return 0;
        }
        int lh = height(root.left);
        int rh = height(root.right);
        
        if (lh == rh) {
            return (1<<lh) + countNodes(root.right);
        } else {
            return (1<<rh) + countNodes(root.left);
        }
        
    }
    
    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        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.