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.如果一個樹是一個完滿(full)二元樹,那麼他的節點數量可以直接由高度計算
出來不需遍歷每個節點(2^h-1)
2.題目給的測資都是完全二元樹,一個完全二元樹未必是一個完滿二元樹,但是
他的左樹必定是一個完滿二元樹。
3.如果當前的樹是一個完滿二元樹(左樹高=右樹高)直接套公式計算,否則對左樹
和右樹遞迴並+1(當前節點)
JavaCode: