47. 六大类二叉树面试题汇总解答 上
0 概述
继上一篇总结了二叉树的基础操作后，这一篇文章汇总下常见的二叉树相关面试题，主要分为判断类、构建类、存储类、查找类、距离类、混合类这六类大问题。
本文所有代码
https://github.com/shishujuan/dsalg/tree/master/code/ds/tree/binary_tree
1 判断类问题
判断类问题主要分下下判断二叉树是否是二叉搜索树、二叉完全树，以及两棵二叉树是否同构这三个问题。
1.1 判断一棵二叉树是否是二叉搜索树(BST)
题：给定一棵二叉树，判断该二叉树是否是二叉搜索树。
二叉搜索树是一种二叉树，但是它有附加的一些约束条件，这些约束条件必须对每个结点都成立：
结点的左子树所有结点的值都小于等于该结点的值。
结点的右子树所有结点的值都大于该结点的值。
结点的左右子树同样都必须是二叉搜索树。
一种错误解法
初看这个问题，容易这么实现：假定当前结点值为 k，对于二叉树中每个结点，判断其左孩子的值是否小于 k，其右孩子的值是否大于 k。如果所有结点都满足该条件，则该二叉树是一棵二叉搜索树。
实现代码如下：
int isBSTError(BTNode *root) { if (!root) return 1; if (root->left && root->left->value >= root->value) return 0; if (root->right && root->right->value < root->value) return 0; if (!isBSTError(root->left) || !isBSTError(root->right)) return 0; return 1; }
很不幸，这种做法是错误的，如下面这棵二叉树满足上面的条件，但是它并不是二叉搜索树。
10 / \ 5 15 -------- binary tree(1) 符合上述条件的二叉树，但是并不是二叉搜索树。 / \ 6 20
解1：蛮力法
上面的错误解法是因为判断不完整导致，可以这样来判断：
判断结点左子树最大值是否大于等于结点的值，如果是，则该二叉树不是二叉搜索树，否则继续下一步判断…
判断右子树最小值是否小于或等于结点的值，如果是，则不是二叉搜索树，否则继续下一步判断。
递归判断左右子树是否是二叉搜索树。（代码中的 bstMax 和 bstMin 函数功能分别是返回二叉树中的最大值和最小值结点，这里假定二叉树为二叉搜索树，实际返回的不一定是最大值和最小值结点）
int isBSTUnefficient(BTNode *root) { if (!root) return 1; if (root->left && bstMax(root->left)->value >= root->value) return 0; if (root->right && bstMin(root->right)->value < root->value) return 0; if (!isBSTUnefficient(root->left) || !isBSTUnefficient(root->right)) return 0; return 1; }
解2：一次遍历法
以前面提到的 binary tree(1) 为例，当我们遍历到结点 15 时，我们知道右子树结点值肯定都 >=10。当我们遍历到结点 15 的左孩子结点 6 时，我们知道结点 15 的左子树结点值都必须在 10 到 15 之间。显然，结点 6 不符合条件，因此它不是一棵二叉搜索树。
int isBSTEfficient(BTNode* root, BTNode *left, BTNode *right) { if (!root) return 1; if (left && root->value <= left->value) return 0; if (right && root->value > right->value) return 0; return isBSTEfficient(root->left, left, root) && isBSTEfficient(root->right, root, right); }
解3：中序遍历解法
还可以模拟树的中序遍历来判断BST，可以直接将中序遍历的结果存到一个辅助数组，然后判断数组是否有序即可判断是否是BST。当然，我们可以不用辅助数组，在遍历时通过保留前一个指针 prev，据此来实现判断BST的解法，初始时 prev = NULL。
int isBSTInOrder(BTNode *root, BTNode *prev) { if (!root) return 1; if (!isBSTInOrder(root->left, prev)) return 0; if (prev && root->value < prev->value) return 0; return isBSTInOrder(root->right, root); }
1.2 判断二叉树是否是完全二叉树
题：给定一棵二叉树，判断该二叉树是否是完全二叉树(完全二叉树定义：若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树）。
解1：常规解法-中序遍历
先定义一个 满结点 的概念：即一个结点存在左右孩子结点，则该结点为满结点。在代码中定义变量 flag 来标识是否发现非满结点，为1表示该二叉树存在非满结点。完全二叉树如果存在非满结点，则根据层序遍历队列中剩下结点必须是叶子结点，且如果一个结点的左孩子为空，则右孩子结点也必须为空。
int isCompleteBTLevelOrder(BTNode *root) { if (!root) return 1; BTNodeQueue *queue = queueNew(btSize(root)); enqueue(queue, root); int flag = 0; while (QUEUE_SIZE(queue) > 0) { BTNode *node = dequeue(queue); if (node->left) { if (flag) return 0; enqueue(queue, node->left); } else { flag = 1; } if (node->right) { if (flag) return 0; enqueue(queue, node->right); } else { flag = 1; } } return 1; }
解2：更简单的方法-判断结点序号法
更简单的方法是判断结点序号法，因为完全二叉树的结点序号都是有规律的，如结点 i 的左右子结点序号为 2i+1 和 2i+2，如根结点序号是 0，它的左右子结点序号是 1 和 2(如果都存在的话)。
我们可以计算二叉树的结点数目，然后依次判断所有结点的序号，如果不是完全二叉树，那肯定会存在结点它的序号大于等于结点数目的。如前面提到的 binary tree(1) 就不是完全二叉树。
10(0) / \ 5(1) 15(2) - 结点数目为5，如果是完全二叉树结点最大的序号应该是4，而它的是6，所以不是。 / \ 6(5) 20(6)
实现代码如下：
int isCompleteBTIndexMethod(BTNode *root, int index, int nodeCount) { if (!root) return 1; if (index >= nodeCount) return 0; return (isCompleteBTIndexMethod(root->left, 2*index+1, nodeCount) && isCompleteBTIndexMethod(root->right, 2*index+2, nodeCount)); }
1.3 判断平衡二叉树
题：判断一棵二叉树是否是平衡二叉树。所谓平衡二叉树，指的是其任意结点的左右子树高度之差不大于1。
__2__ / \ 1 4 ---- 平衡二叉树示例 \ / \ 3 5 6
解1：自顶向下方法
判断一棵二叉树是否是平衡的，对每个结点计算左右子树高度差是否大于1即可，时间复杂度为O(N^2) 。
int isBalanceBTTop2Down(BTNode *root) { if (!root) return 1; int leftHeight = btHeight(root->left); int rightHeight = btHeight(root->right); int hDiff = abs(leftHeight - rightHeight); if (hDiff > 1) return 0; return isBalanceBTTop2Down(root->left) && isBalanceBTTop2Down(root->right); }
解2：自底向上方法
因为解1会重复的遍历很多结点，为此我们可以采用类似后序遍历的方式，自底向上来判断左右子树的高度差，这样时间复杂度为 O(N)。
int isBalanceBTDown2Top(BTNode *root, int *height) { if (!root) { *height = 0; return 1; } int leftHeight, rightHeight; if (isBalanceBTDown2Top(root->left, &leftHeight) && isBalanceBTDown2Top(root->right, &rightHeight)) { int diff = abs(leftHeight - rightHeight); return diff > 1 ? 0 : 1; } return 0; }
1.4 判断两棵二叉树是否同构
题：给定两棵二叉树，根结点分别为 t1 和 t2，判定这两棵二叉树是否同构。所谓二叉树同构就是指它们的结构相同，如下二叉树 (1) 和 (2) 是同构的，而它们和 (3) 是不同结构的：
5 9 6 / \ / \ / \ 1 2 7 12 5 9 / \ / \ \ 4 3 5 8 10 二叉树(1) 二叉树(2) 二叉树(3)
解：二叉树结构是否相同，还是递归实现，先判断根结点是否同构，然后再判断左右子树。
int isOmorphism(BTNode *t1, BTNode *t2) { if (!t1 || !t2) return (!t1) && (!t2); return isOmorphism(t1->left, t2->left) && isOmorphism(t1->right, t2->right); }
2 构建类问题
构建类问题主要是使用二叉树的两种遍历顺序来确定二叉树的另外一种遍历顺序问题。在上一篇文章中我们分析过二叉树的先序、中序、后序遍历的递归和非递归实现。
那么，是否可以根据先序、中序或者先序、后序或者中序、后序唯一确定一棵二叉树呢？
答案是 在没有重复值的二叉树中， 根据先序遍历和后序遍历无法唯一确定一棵二叉树，而根据先序、中序或者中序、后序遍历是可以唯一确定一棵二叉树的。
1）先序和后序遍历无法唯一确定一棵二叉树
一个简单的例子如下，这两棵二叉树的先序遍历和后序遍历相同，由此可以证明先序遍历和后序遍历无法唯一确定一棵二叉树。
1 1 / / 2 2 \ / 3 3 先序遍历：1 2 3 后序遍历：3 2 1
2）先序和中序遍历可以唯一确定二叉树
简单证明：因为先序遍历的第一个元素是根结点，该元素将二叉树中序遍历序列分成两部分，左边（假设有L个元素）表示左子树，若左边无元素，则说明左子树为空；右边（假设有R个元素）是右子树，若为空，则右子树为空。
根据前序遍历中"根-左子树-右子树"的顺序，则由从先序序列的第二元素开始的L个结点序列和中序序列根左边的L个结点序列构造左子树，由先序序列最后R个元素序列与中序序列根右边的R个元素序列构造右子树。
3)中序和后序遍历可以唯一确定二叉树
简单证明: 假定二叉树结点数为 n，假定中序遍历为 S1, S2, …, Sn，而后序遍历为 P1, P2, …, Pn，因为后序遍历最后一个结点 Pn 是根结点，则可以根据 Pn 将中序遍历分为两部分，则其中左边L个结点是左子树结点，右边R个结点是右子树结点，则后序遍历中的 1~L 个结点是左子树的后序遍历，由此 PL 是左子树的根，与前面同理可以将中序遍历分成两部分，直到最终确定该二叉树。
2.1 根据先序、中序遍历构建二叉树
题：给定一棵二叉树的先序和中序遍历序列，请构建该二叉树（注：二叉树没有重复的值）。
先序遍历：7 10 4 3 1 2 8 11 中序遍历：4 10 3 1 7 11 8 2 二叉树如下： 7 / \ 10 2 / \ / 4 3 8 \ / 1 11
解：根据前面的分析来解这个问题。
先序遍历的第一个结点总是根结点。如上图中的二叉树，根结点为 7 。
可以观察到在中序遍历中，根结点7是第 4 个值（从0开始算起）。由于中序遍历顺序为：左子树，根结点，右子树。所以根结点7左边的 {4,10,3,1} 这四个结点属于左子树，而根结点7右边的 {11,8,2} 属于右子树。
据此可以写出递归式了。注意关于如何得到根结点在中序遍历中的位置代码中使用线性扫描查找位置，每次查找需要 O(N) 的时间，整个算法需要 O(N^2) 的时间。如果要提高效率，也可以哈希表来存储与查找根结点在中序遍历中的位置，每次查找只需要 O(1) 的时间，这样构建整棵树只需要 O(N)的时间。
调用方法为 buildBTFromPreInOrder(preorder, inorder, n, 0, n);，其中 preorder 和 inorder 分别为先序中序遍历数组，n 为数组大小。
/** * 辅助函数，查找根结点在中序遍历中的位置。 */ int findBTRootIndex(int inorder[], int count, int rootVal) { int i; for (i = 0; i < count; i++) { if (inorder[i] == rootVal) return i; } return -1; } /** /** * 根据先序和中序遍历构建二叉树 */ BTNode *buildBTFromPreInOrder(int preorder[], int inorder[], int n, int offset, int count) { if (n == 0) return NULL; int rootVal = preorder[0]; int rootIndex = findBTRootIndex(inorder, count, rootVal); int leftCount = rootIndex - offset; // 左子树结点数目 int rightCount = n - leftCount - 1; // 右子树结点数目 BTNode *root = btNewNode(rootVal); root->left = buildBTFromPreInOrder(preorder+1, inorder, leftCount, offset, count); root->right = buildBTFromPreInOrder(preorder+leftCount+1, inorder, rightCount, offset+leftCount+1, count); return root; }
2.2 根据中序、后序遍历构建二叉树
题：给定一棵二叉树的中序和后序遍历序列，请构建该二叉树（注：二叉树没有重复的值）。
中序遍历：4 10 3 1 7 11 8 2 后序遍历：4 1 3 10 11 8 2 7 二叉树如下： 7 / \ 10 2 / \ / 4 3 8 \ / 1 11
解：跟前面一题类似，只是这里根结点是从后序遍历数组的最后一个元素取。
/** * 根据中序和后序遍历构建二叉树 */ BTNode *buildBTFromInPostOrder(int postorder[], int inorder[], int n, int offset, int count) { if (n == 0) return NULL; int rootVal = postorder[n-1]; int rootIndex = findBTRootIndex(inorder, count, rootVal); int leftCount = rootIndex - offset; // 左子树结点数目 int rightCount = n - leftCount - 1; // 右子树结点数目 BTNode *root = btNewNode(rootVal); root->left = buildBTFromInPostOrder(postorder, inorder, leftCount, offset, count); root->right = buildBTFromInPostOrder(postorder+leftCount, inorder, rightCount, offset+leftCount+1, count); return root; }
