Faster than the most voted Java solution


  • 0
    T

    Get the depth of the left sub-tree 'l' and the depth of fully filled level in the right sub-tree 'r'.

    • If they are the same, the tree is fully filled.
    • Otherwise, get the depth of fully filled level in the left tree h. If the left subtree is not filled, check left sub-tree. But be reminded here that the right sub-tree is filled to the previous level. Also, note that the 'l' and 'r' value of the left sub-tree are 'l-1' and 'r-1' now.
    • The case for the left sub-tree is fully filled is similarly handled, but the 'l' value is unknown.
        public int countNodes(TreeNode root) {
            return countNodes(root, 0, 0);
        }
        public int countNodes(TreeNode root, int l, int r) {
            if (root == null) {
                return 0;
            }
            TreeNode node = root;
            if (l == 0) {
                while (node.left != null) {
                    l++;
                    node = node.left;
                }
            }
            node = root;
            if (r == 0) {
                while (node.right != null) {
                    r++;
                    node = node.right;
                }
            }
            if (l == r) {
                return (1<<l+1) - 1;
            }
            int h = 1;
            node = root.left;
            while (node.right != null) {
                h++;
                node = node.right;
            }
            if (h == r) {// left subtree is not full
                return (1<<r) + countNodes(root.left, l-1, h-1);
            } else {
                return (1<<l) + countNodes(root.right, 0, r-1);
            }
        }
    

  • 1
    T

    Attach a non-recursive version for your reference.

        public int countNodes(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int l = 0, r = 0;
            int res = 0;
            
            while (root != null) {
                TreeNode node = root;
                if (l == 0) {
                    while (node.left != null) {
                        l++;
                        node = node.left;
                    }
                }
                node = root;
                if (r == 0) {
                    while (node.right != null) {
                        r++;
                        node = node.right;
                    }
                }
                if (l == r) {
                    return res + (1 << l+1) - 1;
                }
                int h = 1;
                node = root.left;
                while (node.right != null) {
                    h++;
                    node = node.right;
                }
                if (h == r) {// left subtree is not full
                    res += (1 << r);
                    l = l-1;
                    r = h-1;
                    root = root.left;
                } else {
                    res += (1 << l);
                    l = 0;
                    r = r - 1;
                    root = root.right;
                }
            }
            return res;
        }
    

Log in to reply
 

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