29ms c++ binary search solution


  • 0

    first we have a parent node root, like binary search ,it has two choice.

    • First if it's left child is a full binary tree, adding the count of left child's leaf.And then root = root->right, go to it's right child.

    • Second if it's left child isn't a full binary tree, so root = root->left.

    Because this tree is a complete tree, you can find a node , it is a full binary tree.
    '''
    int countNodes(TreeNode* root) {
    int Deep = 0, result = 0;
    if (!root) return 0;
    TreeNode* temp = root, *child = root;//calculate the height of this tree
    while(temp) {
    Deep++;
    temp=temp->left;
    }
    int parentHigh = Deep;//the height of current node

        while (parentHigh>1) {//parentHigh is range 2 to Deep, because 
            child = root->left;//this node's child 
            int childHigh = parentHigh-1;//the height of current node's child 
            for (int i = childHigh; i > 1; i--) child = child->right;//iterate child node from childHigh to 1
            if (child) {//if childtree is a full tree, the child isn't null, so the right child may be not a full tree
                root = root->right;//and then binary search parent's right subtree
                result += 1<<(childHigh-1);//add the count of full binary tree's leaf
            }else{//if not, after iterating child will be null.
                root=root->left;
            }
            parentHigh--;//downward the parent        
        }
        if (root) result++;//if root is full binary tree, you need add the last node
        return result + (1<<(Deep-1))-1;
    }
    

    ''''


Log in to reply
 

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