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