ARTS #017

ARTS是由左耳朵耗子--陈皓发起的一个活动: 每周至少做一个leetcode的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的文章。（也就是Algorithm、Review、Tip、Share简称ARTS），至少坚持一年。

ARTS 017

这是第17篇

Algorihm 算法题

222. Count Complete Tree Nodes

题目难度：中等

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

Note:

Definition of a complete binary tree from :
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^h 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;
 * };
 */

方法1,递归：

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);
    }
}

上面的算法是超时的，看到别人的解法如下：

方法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;
}

实际上上面的两种算法都是递归，但是算法一超时，算法二却正常，运行时间仅为12ms，不明白为什么 if(root->val!=INT_MAX)这个条件会有用，这个条件是必然成立的，为什么加了这个条件就能通过LeetCode的测试用例，不加就会超时？？

方法3：使用迭代

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;
}

这个也会超时，实际上方法一和方法三就是二叉树的遍历，不过在这里都会超时。

方法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);
}

这个算法虽然也用了递归，但是使用了完全二叉树的特征，对于满二叉树数来说计算节点数是很简单的。

方法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);
    }
}

这个算法同样是利用了完全二叉树的特性，理解了注释部分的代码也就理解了整个算法。

Review

参见： https://dandan2009.github.io/2018/11/27/data-structures-part2-a-quick-comparison/

TIPS

再次理解static。

在一个类中的一个方法中声名了如下变量：

static int x;

假设类名是A，然后再实例化出A的对象： a1,a2。这时变量X其实是a1和a2共用的，虽然x是在实例方法中声明的也就是在实例a1中改变了x的值，在a2中也会改下。

虽然这是一个很老的一个知识点，但是在使用static的过程中一不小心就会算错，而且不好排查，所以在使用static之前一定要想清楚。

谷歌云免费送一年：https://cloud.google.com/free/ 注册的时候要有一个外币信用卡，比如visa卡。谷歌为了防止恶意注册，在注册的时候会从信用卡中扣掉一美元，但是过一会就会退款。

https://github.com/tracyone/v2ray.fun 分享个一键整 v2ray 的

https://233yes.com/post/1/ 傻瓜式安装