給出一棵完全二叉樹，求問一共多少個節(jié)點，題目要求復(fù)雜度小于O(n)，不過我用兩種O(logn)*O(logn)的寫法都沒有直接O(n)暴搜來得快。。。
方法一：先DFS，不斷走左子樹的路徑，算出二叉樹層數(shù)max_depth，那么最后一層節(jié)點的數(shù)量為[1, 2^(max_depth-1)]，直接二分這個范圍，然后算出最后一個葉子結(jié)點落在哪里，理論復(fù)雜度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
方法二：直接不斷二分地遞歸找左右子樹，直到遇到某個滿二叉樹節(jié)點，然后sum(左子樹的搜索結(jié)果)+sum(右子樹的搜索結(jié)果)+1（根結(jié)點），理論復(fù)雜度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整棵樹求節(jié)點數(shù)量，復(fù)雜度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