Java short iterative O(log(n)^2) with Binary Search + Bit Manipulation


  • 0
    J
    public class Solution {
        public int countNodes(TreeNode root) {
            if (root == null) return 0;
            // get height
            int h = 0;
            TreeNode p = root;
            while (p.left != null) {
                p = p.left;
                h++;
            }
            // binary search on last level with bit manipulation approach
            int lo = 0;
            int hi = (1 << h) - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                int mask = 1 << h - 1;
                TreeNode n = root;
                for (int i = 0; i < h; i++) {
                    if ((mask & mid) == 0) {
                        n = n.left;
                    } else {
                        n = n.right;
                    }
                    mask >>= 1;
                }
                if (n == null) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }
            return lo + (1 << h) - 1;
        }
    }
    

Log in to reply
 

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