Simulation volume leetcode [normal] 222. number of nodes of complete binary tree

Summary ： Simulation volume Leetcode Summary of questions

222. The number of nodes in a complete binary tree

Here's a tree for you Perfect binary tree The root node root , Find out the number of nodes of the tree .

Perfect binary tree Is defined as follows ： In a complete binary tree , Except that the lowest node may not be full , The number of nodes in each layer reaches the maximum , And the nodes of the lowest layer are concentrated in the leftmost positions of the layer . If the bottom layer is No h layer , Then the layer contains 1~ 2h  Nodes .

Example 1：

Input ：root = [1,2,3,4,5,6]
Output ：6
Example 2：

Input ：root = []
Output ：0
Example 3：

Input ：root = [1]
Output ：1

Tips ：

The number of nodes in the tree ranges from [0, 5 * 104]
0 <= Node.val <= 5 * 104
The topic data ensures that the input tree is Perfect binary tree

Advanced ： Traversing the tree to count nodes is a method with time complexity of O(n) A simple solution . Can you design a faster algorithm ？

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/count-complete-tree-nodes
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Code ：

from leetcode_python.utils import *

def Tree2List(root):
    """ Binary tree  ->  list """
    if not root:return []
    res = []
    last = [root]
    while last:
        now = []
        for node in last:
            if node:
                res.append(node.val)
                now.append(node.left)
                now.append(node.right)
            else:
                res.append(None)
        last = now
    while len(res)>1 and res[-1]==None: res.pop(-1)
    return res

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        return len(Tree2List(root))


def test(data_test):
    s = Solution()
    data = data_test    # normal
    # data = [List2Node(data_test[0])] # list turn node
    return s.getResult(*data)

def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun,data in zip(data_test[0][1::],data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result

if __name__ == '__main__':
    datas = [
        [],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-'*50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{
      time.time() - t0}s')

remarks ：
GitHub：https://github.com/monijuan/leetcode_python

CSDN Summary ： Simulation volume Leetcode Summary of questions

You can add QQ Group communication ：1092754609

leetcode_python.utils See the description on the summary page for details
First brush questions , Then generated by script blog, If there is any mistake, please leave a message , I see it will be revised ！ thank you ！