[LeetCode] 222. Count Complete Tree Nodes

轉自LeetCode

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example:

Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

<Solution>

想法如下

• 這題必須利用 complete binary tree 的特性去解，才不會 TLE

• 關鍵在於，最右邊那個節點，可能有，可能沒有

• 如果最右邊的節點存在，那麼答案就是 (2^h) - 1 個節點

• 如果最右邊的節點不存在，那個答案就是目前這個節點，加上左子樹的節點和右子樹的節點， 1 + countNodes(root.left) + countNodes(root.right)

code如下(參考解法)

Java