vlambda博客
学习文章列表

HALO！我是CW。

第一次见面，不搞太复杂的内容，有关CV领域的内容会在后续输出（先酿一酿，更香~）。这次先分享个算法方面的技巧，相关的数据结构是coder们都熟悉的二叉树，大家怀着轻松愉快的心情当作玩游戏就好。

OK，大家现在就和CW一起来玩玩吧~！

01

—

假设一棵完全二叉树高度为h(h≥1)，其中每个节点按照层序遍历的次序进行编号(从1开始，即根节点的编号为1)，比如像下面这样：

当前你只知道根节点的存在(比如你只能看到上图那棵树中编号为1的节点)，通过根节点你可以到达树中的任意节点，每个节点的数据结构表示为如下形式：

class TreeNode:    def __init__(self, num, left=None, right=None):     # 节点编号     self.num = num     # 左孩子     self.left = left        # 右孩子     self.right = right

脑洞

当然，“勤奋”的孩子会用暴力解法，从根节点出发，将所有路径都搜索一遍(也是不怕累哦..)。不过，CW是叫你来玩游戏的，别搞这种无聊的风格，不好玩

想要好玩，当然得动脑！我们可以脑洞一下，看看根据当前情况，有哪些东西是可以利用的，或者说，根据已知条件可以计算出哪些有利于我们通关的辅助条件。

首先，我们要理解游戏规则，从已知条件中明确一些重要信息。比如，完全二叉树有什么特点？CW觉得，最明显的是：

叶子结点只会出现在最底层和次底层，且最底层的叶子结点仅会集中在树的左部。并且，除最底层以外，其余层的节点数一定达到最大值（当然，最底层的节点数也可能达到最大值，此时的完全二叉树也称为满二叉树）。

来张图更形象些：

另外，按层序遍历的次序来编号就是怎样？CW就引用幼儿园的话术来解释下吧：

对树中的节点按从上至下、从左到右的顺序进行编号

例如：

OK，规则中的术语理解得差不多了，我们不妨大胆些。比如，如果我们知道树中的节点数量为n(n≥1)，那么树中的节点编号范围就是[1, n]，咦！那这岂不是变成了白痴问题了吗..(i大于n的话节点就肯定不存在了)

尽管有些天真，但我们还是可以往这个点上靠：当前已知完全二叉树的高度为h，根据完全二叉树的性质，可知这棵树至少有2^(h-1)个节点、至多有2^h - 1个节点。进一步，这就隐含着：位于最底层的节点，其编号范围为[2^(h-1), 2^h - 1]。

你看啊，看似天真的想法，靠一靠还是能靠出些东西来的。因此，千万不要嘲笑任何一个看似愚蠢的idea，如果你有这种态度，就恰恰说明了你的愚蠢！

既然我们已经计算出最底层节点的编号范围，那么只要确定i与这个范围的关系，差不多就可以通关了：

• 若i ≤ 2^(h-1)，那么节点i一定存在；
• 若i > 2^h - 1，那么节点i一定不存在；
• 若2^(h-1) < i ≤ 2^h - 1，此是节点i位于最底层，需要进一步判断其存在性

于是，我们的目标转为对上述最后一组种情况进行求解。

03

—

04

—

05

—