222. Count Complete Tree Nodes - cocoder39/coco39_LC GitHub Wiki

222. Count Complete Tree Nodes solution 1 the confused part of calculating time complexity is return 1 + countNodes(root->left) + countNodes(root->right), which is the case where the tree rooted with root node is not full. Even though the tree is not full, either its left subtree or right subtree is full. for a full tree the time complexity is O(log n). Thus worst case

T(n) = T(n/2) + 2lgn
       = T(n/4) + 2 lgn + 2 (lgn - 1)
       = ...
       = T(1) + 2 [lgn + (lgn-1) + (lgn-2) + ... + 1]
       = O(lgn*lgn)   (lg n levels and lg n time at each level)

space complexity is O(height) because dfs

int countNodes(TreeNode* root) {
        if (! root) { 
            return 0;
        }
        
        int level = 0;
        TreeNode* left = root;
        TreeNode* right = root;
        while (right) { //log n
            left = left->left;
            right = right->right;
            level++;
        }
        
        if (left == nullptr) {//full
            return (1 << level) - 1;
        }
        
        //full tree has 2^(level - 1) nodes at last level
        //root->left is full if more than 2^(level - 2) nodes at last level
        //root->right is full if no more than 2^(level - 2) nodes at last level
        //T(n) = T(n / 2) + O(log n) = O((log n)^2)
        return 1 + countNodes(root->left) + countNodes(root->right);
    }

solution 2: if leftheight == rightHeight, then left sub tree is full; if leftheight > rightheight, then right sub tree is full. a full tree contains (1 << height) - 1 nodes, be careful that 1 << rightHeight + countNodes(node) => 1 << (rightHeight) + countNodes(node))

public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        TreeNode node = leftHeight == rightHeight ? root.right : root.left;
        return (1 << rightHeight) + countNodes(node);
    }
    
    private int getHeight(TreeNode root) {
        int res = 0;
        TreeNode node = root;
        while (node != null) {
            res++;
            node = node.left;
        }
        return res;
    }

solution 3

public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int level = getHeight(root) - 1;
        double low = 0;
        double high = Math.pow(2, level) - 1;
        while (high - low > 1) {
            double mid = low + (high - low) / 2;
            boolean hasNode = hasNode(root, level, mid);
            if (hasNode) {
                low = mid;
            } else {
                high = mid;
            }
        }
        
        return (int) (Math.pow(2, level) + (hasNode(root, level, high) ? high : low));
    }
    
    private int getHeight(TreeNode root) {
        int res = 0;
        TreeNode node = root;
        while (node != null) {
            res++;
            node = node.left;
        }
        return res;
    }
    
    private boolean hasNode(TreeNode root, int level, double index) {
        TreeNode node = root;
        while (level > 0) {
            double half = Math.pow(2, --level);
            if (index < half) {
                node = node.left;
            } else {
                index -= half;
                node = node.right;
            }
        }
        return node != null;
    }