面试题：如何在完全二叉树中插入一个节点？

题目大意

给定一棵完全二叉树，如何在其中插入一个新节点，并使得新的树仍然保持完全二叉树的性质？请实现一个Insert(Node* root, Node* new_node)方法。

树（Tree）：一种特殊的图。一棵N个节点的树包含恰好N – 1条边，并且任意两点间都连通。

二叉树（Binary Tree）：每个节点至多拥有2个子节点的树。

完全二叉树（Complete Binary Tree）：在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。注意它和满二叉树（Full Binary Tree）的区别。

考察内容

1. 树的表示和遍历，递归

2. 树中的快速查找，二分思想

3. 完全二叉树与满二叉树的区分和联系

题目分析

问题的关键在于，如何在只给定树的形态的前提下（一般来说面试时会给定一个树的根节点指针），快速找到待插入的下一个叶子节点的位置。一个典型的错误解法如下。

解法1：遍历整棵树，每到达一个节点时，先尝试能否插入到左子树中，如果不行再插入到右子树，如此递归下去即可。

这个简单粗暴的做法的问题在于，没有仔细考虑树的形态问题。考虑这样一棵完全二叉树：

新的节点显然应该插入在C的左子树那个位置上。如果每次都尽可能往左边插入的话，新的节点将会插入到D的左子树。

如何修补这个问题？稍加观察可以发现，我们如果可以得到树的深度depth，就可以确定下一个点应该插入在哪一层上。一个直观的想法是，如果遍历的深度超过了depth，就说明当前遍历到了一个非法的位置上，直接返回即可。

解法2：首先递归遍历得到树的深度depth（显然只需要一直往左走）。随后插入一个节点，仍然先插左子树再插右子树，如果发现当前深度超过depth则递归返回。

这是一个近乎完美的做法。唯一的bug在于：我们得到的是原来的树的深度，但是，新的节点的深度不一定在这一层上。考虑一棵满二叉树：

下一个待插入的节点应该在D的左子树上，它的深度应当是4。

所以我们需要对原来的树进行一次特判，如果它已经是一棵满二叉树了，直接把节点插入在最左端，否则就按照上面的方法处理。

如何判断一棵完全二叉树是不是满二叉树？一个简单的做法是，分别往左和往右遍历，观察最左端和最右端的深度是否相等，如果相等则是一棵满二叉树。由于树的深度是logN，所以判满二叉树的复杂度是O(logN)。

解决了这个bug之后，这个算法就没有问题了。但你能看出整个算法的时间复杂度是多少吗？

更好的做法

在最坏情况下（待插入的节点在树的最右端），我们需要遍历整棵树，因此最坏复杂度会达到O(N)。有没有更简洁，效率更高的做法？

考虑一下我们之前算法的瓶颈。当我们遍历到某个节点的时候，做法是先递归查找它的左子树，如果它的左子树无法接收新的节点了，我们才往右子树走。递归的查找使得这个算法在最坏情况下需要一直往右边走，因而需要遍历完整棵树。我们需要试图找到一种更快的方法来判断一个节点的左子树能不能接收新的节点。稍加观察可以发现，一个子树无法接受新的节点当且仅当它是一棵满二叉树（见下图）。

当我们遍历到节点A时，如果发现左子树已经是个满二叉树了，则说明左边已经无法再接受新的节点，这时我们直接往右子树递归查找。而如果左边不是满二叉树，则说明它左边可以接受新的节点，于是我们往左子树递归即可。仍然需要注意的是，如果整棵树本来就已经是一棵满二叉树的话，我们应该直接将节点插在最左端的位置上。

考虑这个算法的时间复杂度。整个遍历的过程会经过logN个节点（为什么？），在每个遍历的节点上都需要做满二叉树的判断。由解法2的分析可以知道，满二叉树的判断是O(logN)的，所以整个算法的复杂度将是O(logN * logN)。

这个算法的代码非常简洁，如下所示。

因此我们用一个简洁、清晰而优秀的算法解决了这个问题。

author: szefany@算法号