小编Ach*_*ane的帖子

上面的函数 AllPaths()将一个包含二叉树每个叶子的路径的数组附加到全局数组中 res。

该代码工作得很好，但我想删除全局变量 res并使函数返回一个数组。我怎样才能做到这一点？

class Node:
    def __init__(self, value, left=None, right=None) -> None:
        self.value = value
        self.left  = left
        self.right = right

res = []
def allPaths(node, arr=[]):
    if node:
        tmp = [*arr, node.value]
        if not node.left and not node.right: # Leaf
            res.append(tmp)
        allPaths(node.left, tmp)
        allPaths(node.right, tmp)


root             = Node(1)
root.left        = Node(2);
root.left.left   = Node(4);
root.left.right  = Node(5);
root.right       = Node(3);
root.right.right = Node(6);
"""
          1         <-- root
        /   \
       2     3  
     /   \    \ …

谁能告诉我下面这个函数的复杂度是多少？以及如何计算复杂度？

我怀疑它是 O(log(n)) 或 O(sqrt(N))。我的推理基于 n=4、n=8、n=16 的示例，我发现循环将采用 log(n) 但我认为这还不够，因为 sqrt 也会给出相同的值所以我需要研究更大的 n 值，所以我不知道如何解决这个问题。

我今天考试的时候有这个功能。

void f(int n){
     int i=1;
     int j=1;
     while(j <= n){
         i += 1;
         j += i;
     }
}