47. 六大类二叉树面试题汇总解答 下
5 距离类问题
5.1 二叉树两个结点之间的最短距离
题：已知二叉树中两个结点，求这两个结点之间的最短距离（注：最短距离是指从一个结点到另一个结点需要经过的边的条数）。
___1___ / \ 2 3 / \ / \ 4 5 6 7 \ 8 Distance(4, 5) = 2 Distance(4, 6) = 4 Distance(3, 4) = 3 Distance(2, 4) = 1 Distance(8, 5) = 5
解：两个结点的距离比较好办，先求出两个结点的最低公共祖先结点（LCA），然后计算 LCA 到两个结点的距离之和即可，时间复杂度 O(N) 。
/** * 计算二叉树两个结点最短距离 */ int distanceOf2BTNodes(BTNode *root, BTNode *p, BTNode *q) { if (!root) return 0; BTNode *lca = btLCADown2Top(root, p, q); int d1 = btDistanceFromRoot(lca, p, 0); int d2 = btDistanceFromRoot(lca, q, 0); return d1+d2; } /** * 计算二叉树结点node和root的距离 */ int btDistanceFromRoot(BTNode *root, BTNode *node, int level) { if (!root) return -1; if (root == node) return level; int left = btDistanceFromRoot(root->left, node, level+1); if (left == -1) return btDistanceFromRoot(root->right, node, level+1); return left; }
5.2 二叉搜索树两个结点的最短距离
题：求一棵二叉搜索树中的两个结点的最短距离。
解：与前面不同的是，这是一棵BST，那么我们可以使用二叉搜索树的特点来简化距离计算流程，当然直接用 5.1 的方法是完全OK的，因为它是通用的计算方法。
/** * 计算BST两个结点最短距离。 */ int distanceOf2BSTNodes(BTNode *root, BTNode *p, BTNode *q) { if (!root) return 0; if (root->value > p->value && root->value > q->value) { return distanceOf2BSTNodes(root->left, p, q); } else if(root->value <= p->value && root->value <= q->value){ return distanceOf2BSTNodes(root->right, p, q); } else { return bstDistanceFromRoot(root, p) + bstDistanceFromRoot(root, q); } } /** * 计算BST结点node和root的距离 */ int bstDistanceFromRoot(BTNode *root, BTNode *node) { if (root->value == node->value) return 0; else if (root->value > node->value) return 1 + bstDistanceFromRoot(root->left, node); else return 1 + bstDistanceFromRoot(root->right, node); }
5.3 二叉树中结点的最大距离
题：写一个程序求一棵二叉树中相距最远的两个结点之间的距离。
解：《编程之美》上有这道题，这题跟前面不同，要求相距最远的两个结点的距离，而且并没有指定两个结点位置。计算一个二叉树的最大距离有两个情况:
路径为 左子树的最深节点 -> 根节点 -> 右子树的最深节点。
路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。
___10___ / \ _5_ 15 ------ 第1种情况 / \ \ 1 8 7 10 / 5 / \ ------ 第2种情况 1 8 / \ 2 3
我们定义函数 maxDistanceOfBT(BTNode *root) 用于计算二叉树相距最远的两个结点的距离，可以递归的先计算左右子树的最远结点距离，然后比较左子树最远距离、右子树最远距离以及左右子树最大深度之和，从而求出整个二叉树的相距最远的两个结点的距离。
int btMaxDistance(BTNode *root, int *maxDepth) { if (!root) { *maxDepth = 0; return 0; } int leftMaxDepth, rightMaxDepth; int leftMaxDistance = btMaxDistance(root->left, &leftMaxDepth); int rightMaxDistance = btMaxDistance(root->right, &rightMaxDepth); *maxDepth = max(leftMaxDepth+1, rightMaxDepth+1); int maxDistance = max3(leftMaxDistance, rightMaxDistance, leftMaxDepth+rightMaxDepth); // max求两个数最大值，max3求三个数最大值，详见代码 return maxDistance; }
5.4 二叉树最大宽度
题：给定一棵二叉树，求该二叉树的最大宽度。二叉树的宽度指的是每一层的结点数目。如下面这棵二叉树，从上往下1-4层的宽度分别是 1，2，3，2，于是它的最大宽度为3。
1 / \ 2 3 / \ \ 4 5 8 / \ 6 7
解1：层序遍历法
最容易想到的方法就是使用层序遍历，然后计算每一层的结点数，然后得出最大结点数。该方法时间复杂度为 O(N^2)。当然如果优化为使用队列来实现层序遍历，可以得到 O(N) 的时间复杂度。
/** * 二叉树最大宽度 */ int btMaxWidth(BTNode *root) { int h = btHeight(root); int level, width; int maxWidth = 0; for (level = 1; level <= h; level++) { width = btLevelWidth(root, level); if (width > maxWidth) maxWidth = width; } return maxWidth; } /** * 二叉树第level层的宽度 */ int btLevelWidth(BTNode *root, int level) { if (!root) return 0; if (level == 1) return 1; return btLevelWidth(root->left, level-1) + btLevelWidth(root->right, level-1); }
解2：先序遍历法
我们可以先创建一个大小为二叉树高度 h 的辅助数组来存储每一层的宽度，初始化为0。通过先序遍历的方式来遍历二叉树，并设置好每层的宽度。最后，从这个辅助数组中求最大值即是二叉树最大宽度。
/** * 二叉树最大宽度-先序遍历法 */ int btMaxWidthPreOrder(BTNode *root) { int h = btHeight(root); int *count = (int *)calloc(sizeof(int), h); btLevelWidthCount(root, 0, count); int i, maxWidth = 0; for (i = 0; i < h; i++) { if (count[i] > maxWidth) maxWidth = count[i]; } return maxWidth; } /** * 计算二叉树从 level 开始的每层宽度，并存储到数组 count 中。 */ void btLevelWidthCount(BTNode *root, int level, int count[]) { if (!root) return; count[level]++; btLevelWidthCount(root->left, level+1, count); btLevelWidthCount(root->right, level+1, count); }
6 混合类问题
此类问题主要考察二叉树和链表/数组等结合，形式偏新颖。
6.1 根据有序数组构建平衡二叉搜索树
题：给定一个有序数组，数组元素升序排列，试根据该数组元素构建一棵平衡二叉搜索树（Balanced Binary Search Tree）。所谓平衡的定义，就是指二叉树的子树高度之差不能超过1。
__3__ / \ 1 5 ---- 平衡二叉搜索树示例 \ / \ 2 4 6
解：如果要从一个有序数组中选择一个元素作为根结点，应该选择哪个元素呢？我们应该选择有序数组的中间元素作为根结点。选择了中间元素作为根结点并创建后，剩下的元素分为两部分，可以看作是两个数组。这样剩下的元素在根结点左边的作为左子树，右边的作为右子树。
BTNode *sortedArray2BST(int a[], int start, int end) { if (start > end) return NULL; int mid = start + (end-start)/2; BTNode *root = btNewNode(a[mid]); root->left = sortedArray2BST(a, start, mid-1); root->right = sortedArray2BST(a, mid+1, end); return root; }
6.2 有序单向链表构建平衡二叉搜索树
题：给定一个有序的单向链表，构建一棵平衡二叉搜索树。
解：最自然的想法是先将链表中的结点的值保存在数组中，然后采用 6.1 中方法实现，时间复杂度为 O(N)。我们还可以采用自底向上的方法，在这里我们不再需要每次查找中间元素。
下面代码依旧需要链表长度作为参数，计算链表长度时间复杂度为O(N)，算法时间复杂度也为O(N)，所以总的时间复杂度为O(N)。
代码中需要注意的是每次调用 sortedList2BST 函数时，list 位置都会变化，调用完函数后 list 总是指向 mid+1 的位置 （如果满足返回条件，则 list 位置不变）。
BTNode *sortedList2BST(ListNode **pList, int start, int end) { if (start > end) return NULL; int mid = start + (end-start)/2; BTNode *left = sortedList2BST(pList, start, mid-1); BTNode *parent = btNewNode((*pList)->value); parent->left = left; *pList = (*pList)->next; parent->right = sortedList2BST(pList, mid+1, end); return parent; }
例如链表只有2个节点 3->5->NULL，则初始 start=0, end=1, mid=0，继而递归调用 sortedList2BST(pList, start,mid-1)，此时直接返回 NULL。即左孩子为NULL， 根结点为 3，而后链表指向 5，再调用 sortedList2BST(pList, mid+1, end)，而这次调用返回结点 5，将其赋给根结点 3 的右孩子。这次调用的 mid=1，调用完成后 list 已经指向链表末尾。
6.3 二叉搜索树转换为有序循环链表
题：给定一棵二叉搜索树(BST)，将其转换为双向的有序循环链表。
解：如图所示，需要将 BST 的左右孩子指针替换成链表的 prev 和 next 指针，分别指向双向链表的前一个和后一个结点。相信大多数人第一反应就是中序遍历这棵二叉树，同时改变树中结点的 left 和 right 指针。这里需要额外考虑的是如何将最后一个结点的right 指针指向第一个结点，如下图所展示的那样。
以中序遍历遍历一棵二叉树的时候，每遍历到一个结点，我们就可以修改该结点的left指针指向前一个遍历到的结点，因为在后续操作中我们不会再用到 left 指针；与此同时，我们还需要修改前一个遍历结点的 right 指针，让前一个遍历结点的 right 指针指向当前结点。
比如我们遍历到结点2，则我们修改结点2的 left 指针指向结点1，同时需要修改结点1的 right 指针指向结点2。需要注意一点，这里的前一个遍历结点不是当前结点的父结点，而是当前结点的前一个比它小的结点。
看似问题已经解决，慢着，我们其实落下了重要的两步。1）我们没有对头结点head赋值。2）最后一个结点的right指针没有指向第一个结点。
解决这两个问题的方案非常简单：在每次递归调用的时候，更新当前遍历结点的 right 指针让其指向头结点 head，同时更新头结点 head 的 left 指针让其指向当前遍历结点。当递归调用结束的时候，链表的头尾结点会指向正确的位置。不要忘记只有一个结点的特殊情况，它的 left 和 right 指针都是指向自己。
void bt2DoublyList(BTNode *node, BTNode **pPrev, BTNode **pHead) { if (!node) return; bt2DoublyList(node->left, pPrev, pHead); // 当前结点的left指向前一个结点pPrev node->left = *pPrev; if (*pPrev) (*pPrev)->right = node; // 前一个结点的right指向当前结点 else *pHead = node; // 如果前面没有结点，则设置head为当前结点（当前结点为最小的结点）。 // 递归结束后，head的left指针指向最后一个结点，最后一个结点的右指针指向head结点。 // 注意保存当前结点的right指针，因为在后面代码中会修改该指针。 BTNode *right = node->right; (*pHead)->left = node; node->right = (*pHead); *pPrev = node;//更新前一个结点 bt2DoublyList(right, pPrev, pHead); }
这个解法非常的精巧，因为该算法是对中序遍历的一个改进，因此它的时间复杂度为O(N)，N为结点数目。当然，相比中序遍历，我们在每次递归调用过程中增加了额外的赋值操作。
