ARTSDecember 2, 2018 at 04:52 AM作者单一鸣2 分钟阅读3 个标签

ARTS #017

ARTS is an activity initiated by 由左耳朵耗子--陈皓: Do at least one leetcode algorithm question every week, read and comment on at least one English technical article, learn at least one technical skill, and share an article with opinions and thoughts. (That is, Algorithm, Review, Tip, and Share are referred to as ARTS) and persist for at least one year.

ARTS 017

This is article 17

Algorihm algorithm question

222. Count Complete Tree Nodes

Question Difficulty: Medium

Given a complete binary tree, count the number of nodes.

Note:

<u style=“display: inline;”>Definition of a complete binary tree from :</u> In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2<sup>h</sup> nodes inclusive at the last level h.

Example:

**Input:** 
    1
   / \
  2   3
 / \  /
4  5 6

**Output:** 6```



#### Solution

Language: **C**

```c
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

Method 1, recursive:

int countNodes(struct TreeNode* root) {
        if (!root) {
        return 0;
    }

    int count = 1;
    if (root->left) {
        count +=countNodes(root->left);
    }
    if (root->right) {
        count +=countNodes(root->right);
    }
}

The above algorithm is timed out. I saw other people’s solutions as follows:

Method 2:

int countNodes(struct TreeNode* root) {
    if(!root) return 0;
    if(root->val!=INT_MAX){
        root->val=INT_MAX;
        return 1+countNodes(root->left)+countNodes(root->right);
    }
    return -1111111;
}

In fact, the above two algorithms are both recursive, but algorithm one times out, but algorithm two is normal, and the running time is only 12ms. I don’t understand why the condition if (root->val!=INT_MAX) is useful. This condition is definitely true. Why can the test case of LeetCode be passed if this condition is added, but it will time out if it is not added? ?

Method 3: Use iteration

int countNodes(struct TreeNode* root) {
    if (!root) {
        return 0;
    }
  struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * (1000));
    int count = 0;
    int index = 0;
    struct TreeNode* p= root;
    
    while (p) {
        ++count;
        printf("%d,%d=;;;;",count,p->val);
        if (p->right) {
            printf("ooooooo");
            stack[index++] = p->right;
        }
        
        p = p->left;
        
        if (!p && index > 0) {
            printf("kkkkkkkkkkk");
            p =  stack[--index];
        }
    }
    
    return count;
}

This will also time out. In fact, methods one and three are binary tree traversals, but they will all time out here.

Method 4:

int countNodes(struct TreeNode* root)
{
    /* get left depth and right depth */
    struct TreeNode *pL = root, *pR = root;
    int dep = 0;
    for(; pL && pR; dep++)
    {
        pL = pL->left;
        pR = pR->right;
    }
    
    /* count the full tree collectively */
    if(!pL && !pR) return (1<<dep) -1;
    
    /* count left and right sub-trees separately */
    return countNodes(root->left) + 1 + countNodes(root->right);
}

Although this algorithm also uses recursion, it uses the characteristics of a complete binary tree. It is very simple to calculate the number of nodes for a full binary tree.

Method 5


int height(struct TreeNode *root)
{
    int h;
    
    h = -1;
    while (root) {
        ++h;
        root = root->left;
    }
    return h;
}

int countNodes(struct TreeNode* root)
{
    int h1, h2;
    
    
    if (!root) return 0;
    
    h1 = height(root->left);
    h2 = height(root->right);
    
    if (h1 == h2) {
        //说明左子树是满树 (1 << (h1 + 1)) - 1) 是左子树节点的个数
        return 1 + ((1 << (h1 + 1)) - 1) + countNodes(root->right);
    } else {
         //说明右子树是满树 ，((1 << h1) - 1) 是右子树节点的个数
        return 1 + ((1 << h1) - 1) + countNodes(root->left);
    }
}

This algorithm also takes advantage of the characteristics of a complete binary tree. If you understand the code in the comment part, you will understand the entire algorithm.

Review

TIPS

Understand static again.

The following variables are declared in a method in a class:

static int x;

Assume that the class name is A, and then instantiate the objects of A: a1, a2. At this time, the variable

Although this is a very old knowledge point, you may make miscalculations accidentally when using static, and it is difficult to troubleshoot, so you must think clearly before using static.

Google Cloud is free for one year: https://cloud.google.com/free/ When registering, you must have a foreign currency credit card, such as a visa card. In order to prevent malicious registration, Google will deduct one dollar from the credit card when registering, but will refund it after a while.

https://github.com/tracyone/v2ray.fun shared one-click v2ray

https://233yes.com/post/1/ Fool-proof installation

FAQ