※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 222. Count Complete Tree Nodes
: 給你一個完全二元樹，判斷該二元樹共有幾個節點。
: 限制：你必須設計一個小於O(n)時間的演算法。
: https://assets.leetcode.com/uploads/2021/01/14/complete.jpg
: Input: root = [1,2,3,4,5,6]
: Output: 6
思路:
1.觀察 complete binary tree 如果 root 是 1 並且 node.val 代表前面有幾個 node
往左子樹走 node.val 會 *2 往右會 *2+1
目標就可以變成想辦法走到最下排最右邊的那個 node 並且邊走邊算
2.要怎麼知道最下最右的 node 在左子樹還是右子樹?
可以用借用 complete binary tree 的性質 用左子樹樹高和右子樹樹高判斷
如果相等就會在右子樹 反之則在左子樹
樹高可以直接走左邊走到底得到 問就是性質
所以流程就是 對每個 node 看 node.left 和 node.right 往左走能走多深
因為右邊一定不會比左邊高 所以可以一起走 看右邊走到底時左邊還有沒有東西
兩個高度一樣就往右 res = res*2+1 反之往左 res = res*2
直到找到最下最右的 node
複雜度是 log(n) 層 * 每層決定要走左右也是 log(n) = O(log(n)^log(n))
3.
Python code:
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
res = 1 if root else 0
node = root
while node:
L, R = node.left, node.right
if not L and not R:
break
while R:
L = L.left
R = R.left
res = res*2 if L else res*2+1
node = node.left if L else node.right
return res
今天沒有龍大