Concise Elegant C++ Solution Beats 99% With Detailed Comments


  • 1
    R
    /* since the tree is complete the height of the tree */
    /* is the height of the left most node */
    int HeightCompleteTree(TreeNode * root) {
        if (!root) { return 0; }
        return HeightCompleteTree(root->left) + 1;
    }
    
    int countNodes(TreeNode* root) {
        if (!root) { return 0; }
        int cur_count = 1;
        TreeNode* next = root;
        /* just like binary search, during each iteration we get a reference of the */
        /* root of the subtree where the LAST NODE of the complete binary tree resides in */
        /* while we are doing that we also calculate the current node count as if that node is */
        /* the last node, the iteration terminates when the root of the subtree is the last node itself,
         * by that time we know the count of the nodes already */
        while (next->left || next->right) {
    
            /* this means the LAST NODE is at the left subtree */
            if (HeightCompleteTree(next->left) > HeightCompleteTree(next->right)) {
                next = next->left;
                /* update the current count */
                cur_count = cur_count << 1;
            } else {
                next = next->right;
                /* update the current count */
                cur_count = (cur_count << 1) + 1;
            }
    
        }
    
        /* while loop terminate when "next" is the LAST NODE */
        return cur_count;
    }
    

  • 0
    B

    Elegant codes, thanks for sharing~


Log in to reply
 

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