casyup.me@outlook.com

0%

leetcode/222CountCompleteTreeNodes

Posted on

222. Count Complete Tree Nodes

统计 complete tree 节点数量

my solution

首先说说我的做法, 我首先想到的是用栈来保存其数据结构, 跟踪路径, 从右至左, 直到找到一条能到达底层的路

first. my idea is use stack to save the data structure, trace the route, from right to left, until find a way to bottom node

(前些天被一个 13 说我 leetcode 从不写注释, 我怨念到了现在 = =)

(I was told by a 13 the other day that i never write comments in leetcode. I remember it till now :( )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public:
    int countNodes(TreeNode* root) {
        stack<pair<TreeNode*, bool>> nodes;
        
        TreeNode* cursor = root;
        int ldeep = 0, rdeep = 0;
        while (cursor) {
            cursor = cursor->left;
            ++ldeep;
        }
        cursor = root;
        while (cursor) {
            // 1 means next is a right node
            nodes.push(make_pair(cursor, 1));
            cursor = cursor->right;
            ++rdeep;
        }
        int ret = (1 << ldeep) - 1;
        // is a full binary tree
        if (ldeep == rdeep) 
            return ret;
        
        while (!nodes.empty()) {
            cursor = nodes.top().first;
            if (!cursor->right) --ret;
            if (!cursor->left) --ret;
            if (cursor->left || cursor->right)
                return ret;
            
            nodes.pop();
            --rdeep;
            // current node is right node, so next node is left node
            if (!nodes.empty() && nodes.top().second) {
                nodes.top().second = 0;
                nodes.push(make_pair(nodes.top().first->left, 1));
                ++rdeep;
                continue;
            }
            
            // find next node with next node is right node
            while (!nodes.empty() && !nodes.top().second) {
                nodes.pop();
                --rdeep;
            }
            // means some errors occur
            if (nodes.empty()) return -1;
            nodes.top().second = 0;
            cursor = nodes.top().first->left;
            while (cursor) {
                nodes.push(make_pair(cursor, 1));
                cursor = cursor->right;
                ++rdeep;
            }
            // get the bottom element
            if (ldeep == rdeep) return ret;
        }
        
        // means some errors occur
        return -2;
    }
};

最不理想的情况下, 最左边只有一个节点, 会遍历掉所有节点 = =. stack 容量应该不会超过 31 个元素.

代码不够整洁, 不够易懂. 勉强算个解法.

best solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
inline bool is_high (TreeNode* root, int path, int high) {
    high--;
    while (high >= 0) {
        bool flag = path & (1 << high);
        if (flag && root->right) {
            root = root->right;
        } else if (!flag && root->left) {
            root = root->left;
        } else {
            return false;
        }
        high--;
    }

    return true;
}

class Solution {
public:
    int countNodes (TreeNode* root) {
        if (!root) return 0;

        int high = 0;
        TreeNode* node = root->left;
        while (node) {
            high++;
            node = node->left;
        }

        int first = 0;
        int last = 1 << high;
        while (first < last) {
            int mid = (first + last) / 2;
            if (is_high(root, mid, high)) {
                first = mid + 1;        
            } else {
                last = mid;
            }
        }

        return (1 << high) - 1 + last;
    }
};

最后的 return 里面, 用 first 和 last 都可以, 我觉得 last 语义可能更好, 所以换成了 last.

on the end of return, use both first and last. i think ‘last’ more make sence, so i use ‘last’

他的计算是 full tree 节点数 + 底层节点数. 从这个算法中我学到了一些东西, 二进制和 binary tree, 真的有很大可操作空间.

the algorithm is a number of full tree nodes plus bottom nodes. I study something from the algorithm. it’s a lot of skill can use between binary system and binary tree.

在分析算法前, 我先总结一下我从这个算法中看到的规律.

before profiling this algorithm, summarize some rules of complete tree that I saw in this algorithm

首先, 将树节点排序, root 为 1, 从左到右, 从上到下, 依次递进. 得到类似的图 :

first, sort tree nodes. root is number 1, from left to right, up to down, get this map:

                            1
            2                                3
    4                5                6                7
8(1)    9(2)    10(3)    11(4)    12(5)    13(6)    14(7)    15(8)

假设一个数, 5, 其二进制为 101, 已知是 binary tree, 所以每个节点的 2 倍就是当前数字右移 1 位, 右尾置 0. 所以 0 代表向左下前进, 1 则代表向右下前进. 分为两种情况.

assume a number, for example 5, it’s binary expression is 101.

  1. 将首位看做无效位, 则 101 = 01, 代表从根向左->向右, 则得到了数字 5.

    treat the first digit as an invalid bit. 101 means left -> right. get the number 5.

  2. 将首位看做有效位, 则 101 = 101, 代表从根向右->向左->向右, 得到数字 13, 而这个数字, 刚好是底部从左往右的第 5 个数字 + 1 = 第 6 个数字.

    treat the first digit as an valid bit. 101 means right -> left -> right. get the number 13. the number sorted by bottom level is the the original number plus one.

    (为什么呢? 为什么刚好是 + 1? 因为恒定的, 因为这是 complete tree, 每一层到下一层的相对应那个数的步数都是恒定的. 都是 (2 << n) - 1, 而 + 1 就刚好是 2 << n, 这和刚才将首位看做有效位对应上了, 其实将首位看做有效位也就是增加了 2 << n 而已.)

将一些规律总结后, 就变简单了许多

after summarize some rules, things more simple. 

1
2
3
4
5
6
7
8
while (first < last) {
    int mid = (first + last) / 2;
    if (is_high(root, mid, high)) {
        first = mid + 1;        
    } else {
        last = mid;
    }
}

这段代码就是在首位间不断逼近, 求得的最大的数字, 也就是最后一排.

this code just get more close between ‘first’ and ‘last’. get biggest number, also is the result.

is_high(root, mid, high) 实则是在判断, 最后一排有没有 mid + 1 这个数字, 如果有, 则 first = mid + 1, 意味着这个数字是存在的, 继续不断逼近. 直到最后 last == first, 因为 first = mid + 1, 而 mid = (first + last) / 2, 所以 first 最大不会超过 last.

‘is_higt’ judge is there a number ‘mid + 1’. if is, then ‘first = mid + 1’. means this number is exist.

所以这个解法是利用了 complete tree 的特性. 相当简洁, 也没有使用额外的空间, 时间复杂度是 O(logn), 很不错的解法.

I’m tired… :(

thanks for browsing :)