※ 引述《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
今天没有龙大