Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2022-11-15 09:32:19
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:
作者: int0x80 (請逐項修改)   2022-11-15 12:10:00
好強

Links booklink

Contact Us: admin [ a t ] ucptt.com