给出一棵完全二叉树，求问一共多少个节点，题目要求复杂度小于O(n)，不过我用两种O(logn)*O(logn)的写法都没有直接O(n)暴搜来得快。。。
方法一：先DFS，不断走左子树的路径，算出二叉树层数max_depth，那么最后一层节点的数量为[1, 2^(max_depth-1)]，直接二分这个范围，然后算出最后一个叶子结点落在哪里，理论复杂度O(logn)*O(logn)
1 #222
2 #Runtime: 156 ms
3 #Memory Usage: 29.2 MB
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def binarySearch(self, root, depth, mid, l, r):
13 if depth == self.max_depth - 1:
14 if root:
15 return True
16 return False
17 if mid <= (l + r)//2:
18 return self.binarySearch(root.left, depth + 1, mid, l, (l + r)//2)
19 else:
20 return self.binarySearch(root.right, depth + 1, mid, (l + r)//2, r)
21
22 def countNodes(self, root):
23 """
24 :type root: TreeNode
25 :rtype: int
26 """
27 self.max_depth = 0
28 rt = root
29 while rt:
30 rt = rt.left
31 self.max_depth = self.max_depth + 1
32 if not self.max_depth:
33 return 0
34 l = 1
35 r = 2**(self.max_depth - 1)
36 while l < r:
37 mid = (l + r) // 2 + (l + r) % 2
38 if self.binarySearch(root, 0, mid, 1, 2**(self.max_depth - 1)):
39 l = mid
40 else:
41 r = mid - 1
42 return l + 2**(self.max_depth - 1) - 1
方法二：直接不断二分地递归找左右子树，直到遇到某个满二叉树节点，然后sum(左子树的搜索结果)+sum(右子树的搜索结果)+1（根结点），理论复杂度O(logn)*O(logn)
1 #222
2 #Runtime: 137 ms
3 #Memory Usage: 29.2 MB
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def DFS(self, root, fg):
13 if not root:
14 return 1
15 if fg == 0:
16 return self.DFS(root.left, 0) + 1
17 return self.DFS(root.right, 1) + 1
18
19 def countNodes(self, root):
20 """
21 :type root: TreeNode
22 :rtype: int
23 """
24 if not root:
25 return 0
26 depth_l = self.DFS(root.left, 0)
27 depth_r = self.DFS(root.right, 1)
28 if depth_l == depth_r:
29 return 2**depth_l - 1
30 return self.countNodes(root.left) + self.countNodes(root.right) + 1
方法三：直接DFS整棵树求节点数量，复杂度O(n)，没想到这个方法反而最快...
1 #222
2 #Runtime: 87 ms
3 #Memory Usage: 29.4 MB
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def DFS(self, root):
13 if not root:
14 return
15 self.ans += 1
16 self.DFS(root.left)
17 self.DFS(root.right)
18
19 def countNodes(self, root):
20 """
21 :type root: TreeNode
22 :rtype: int
23 """
24 self.ans = 0
25 self.DFS(root)
26 return self.ans