Fast Java solution 52mm beating 98.57%


  • 2
    J

    Binary search. Nothing special.

    public class Solution {
        public int countNodes(TreeNode root) {
            if (root == null) {
                return 0;
            }
            TreeNode node = root.left;
            int height = 0;
            while (node != null) {
                node = node.left;
                height++;
            }
            int level = 0;
            int depth = 0;
            int count = 0;
            while (root != null) {
                depth = level;
                node = root.left;
                if (node == null) {
                    break;
                }
                while (node != null) {
                    node = node.right;
                    depth++;
                }
                level++;
                if (depth == height) {
                    root = root.right;
                    count += 1 << (height - level);
                }
                else {
                    root = root.left;
                }
            }
            if (root != null && level == height) {
                count++;
            }
            return (1 << height) - 1 + count; 
        }
    }

Log in to reply
 

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