用O(n)的时间复杂度就不说了，这里说用小于O(n)的时间复杂度。
def nums_node(root): if not root: return None return bs(root,1,max_height(root,1)) def bs(node,level,height): #开始level=1 #height是一个不变的值，可以看做是一个全局变量，代表树的最大深度。 if level==height: return 1 #如果右边子树的最左节点到底了 #说明左边子树是满二叉树 if max_height(root.right,depth+1)==height: return (2**(height-level))+bs(node.right, level+1, height) else: #那么左子树不是满二叉树，但是右子树的上一行是满二叉树 return (2**(height-level-1))+bs(node.left, level+1, height) def max_height(node,level): while node: node=node.left level+=1 return level-1