47. 六大类二叉树面试题汇总解答 中
3 存储类问题
3.1 二叉搜索树存储和恢复
题：设计一个算法，将一棵二叉搜索树（BST）保存到文件中，需要能够从文件中恢复原来的二叉搜索树，注意算法的时空复杂度。
30 / \ 20 40 / / \ 10 35 50
思路
二叉树遍历算法有先序遍历、中序遍历、后序遍历算法等。但是它们中间哪一种能够用于保存BST到文件中并从文件中恢复原来的BST，这是个要考虑的问题。
假定用中序遍历，因为这棵BST的中序遍历为 10 20 30 35 40 50，可能的结构是下面这样，因此 中序遍历不符合要求 。
50 / 40 / 35 / 30 / 20 / 10
既然中序遍历不行，后序遍历如何？后序遍历该BST可以得到：10 20 35 50 40 30 。读取这些结点并构造出原来的BST是个难题，因为在构造二叉树时是先构造父结点再插入孩子结点，而后序遍历序列是先读取到孩子结点然后才是父结点，所以 后续遍历也不符合条件 。
综合看来，只有先序遍历满足条件 。该BST的先序遍历是 30 20 10 40 35 50 。我们观察到重要的一点就是：一个结点的父亲结点总是在该结点之前输出 。有了这个观察，我们从文件中读取BST结点序列后，总是可以在构造孩子结点之前构造它们的父结点。将BST写入到文件的代码跟先序遍历一样。
那么读取恢复怎么做呢？使用二叉搜索树 bstInsert() 方法执行 N 次插入操作即可，如果二叉搜索树平衡的话每次插入需要时间 O(lgN)，共需要 O(NlgN) 的时间，而最坏情况下为 O(N^2)。
/** * 存储二叉树到文件中-使用先序遍历 */ void bstSave(BTNode *root, FILE *fp) { if (!root) return; char temp[30]; sprintf(temp, "%d\n", root->value); fputs(temp, fp); bstSave(root->left, fp); bstSave(root->right, fp); } /** * 从文件中恢复二叉树 */ BTNode *bstRestore(FILE *fp) { BTNode *root = NULL; char *s; char buf[30]; while ((s = fgets(buf, 30, fp))) { int nodeValue = atoi(s); root = bstInsert(root, nodeValue); } return root; }
3.2 二叉树存储和恢复
题：设计一个算法能够实现二叉树（注意，不是二叉搜索树BST）存储和恢复。
解：3.1节提到过使用先序遍历可以保存和恢复二叉搜索树，而这个题目是针对二叉树，并不是BST，所以不能用前面的方式。不过，我们可以采用先序遍历的思想，只是在这里需要改动。为了能够在重构二叉树时结点能够插入到正确的位置，在使用先序遍历保存二叉树到文件中的时候需要把 NULL 结点也保存起来（可以使用特殊符号如 # 来标识 NULL 结点）。
注意：本题采用 # 保存 NULL 结点的方法存在缺陷，如本方法中二叉树结点值就不能是 #。如果要能保存各种字符，则需要采用其他方法来实现了。
30 / \ 10 20 / / \ 50 45 35
如上面这棵二叉树，保存到文件中则为 30 10 50 # # # 20 45 # # 35 # #。于是，保存和恢复实现的代码如下：
/** * 存储二叉树到文件中 */ void btSave(BTNode *root, FILE *fp) { if (!root) { fputs("#\n", fp); } else { char temp[30]; sprintf(temp, "%d\n", root->value); fputs(temp, fp); btSave(root->left, fp); btSave(root->right, fp); } } /** * 从文件恢复二叉树 */ BTNode *btRestore(BTNode *root, FILE *fp) { char buf[30]; char *s = fgets(buf, 30, fp); if (!s || strcmp(s, "#\n") == 0) return NULL; int nodeValue = atoi(s); root = btNewNode(nodeValue); root->left = btRestore(root->left, fp); root->right = btRestore(root->right, fp); return root; }
4 查找类问题
查找类问题主要包括：查找二叉树/二叉搜索树的最低公共祖先结点，或者是二叉树中的最大的子树且该子树为二叉搜索树等。
4.1 二叉搜索树最低公共祖先结点
题：给定一棵二叉搜索树(BST)，找出树中两个结点的最低公共祖先结点(LCA)。如下面这棵二叉树结点 2 和 结点 8 的 LCA 是 6，而结点 4 和 结点 2 的 LCA 是 2。
______6______ / \ __2__ __8__ / \ / \ 0 4 7 9 / \ 3 5
解：我们从顶往下遍历二叉搜索树时，对每个遍历到的结点，待求LCA的两个结点可能有如下四种分布情况：
两个结点都在树的左子树中：LCA一定在当前遍历结点的左子树中。
两个结点都在树的右子树中：LCA一定在当前遍历结点右子树中。
一个结点在树的左边，一个结点在树的右边：LCA就是当前遍历的结点。
当前结点等于这两个结点中的一个：LCA也是当前遍历的结点。
BTNode *bstLCA(BTNode *root, BTNode *p, BTNode *q) { if (!root || !p || !q) return NULL; int maxValue = p->value >= q->value ? p->value : q->value; int minValue = p->value < q->value ? p->value : q->value; if (maxValue < root->value) { return bstLCA(root->left, p, q); } else if (minValue > root->value) { return bstLCA(root->right, p, q); } else { return root; } }
4.2 二叉树(不一定是BST）最低公共祖先结点
题：给定二叉树中的两个结点，输出这两个结点的最低公共祖先结点（LCA）。注意，该二叉树不一定是二叉搜索树。
_______3______ / \ ___5__ ___1__ / \ / \ 6 2 0 8 / \ 7 4
解1：自顶向下方法
因为不一定是BST，所以不能根据值大小来判断，不过总体思路是一样的：我们可以从根结点出发，判断当前结点的左右子树是否包含这两个结点。
如果左子树包含两个结点，则它们的最低公共祖先结点也一定在左子树中。
如果右子树包含两个结点，则它们的最低公共祖先结点也一定在右子树中。
如果一个结点在左子树，而另一个结点在右子树中，则当前结点就是它们的最低公共祖先结点。
因为对每个结点都要重复判断结点 p 和 q 的位置，总的时间复杂度为 O(N^2)，为此，我们可以考虑找一个效率更高的方法。
/** * 二叉树最低公共祖先结点-自顶向下解法 O(N^2) */ BTNode *btLCATop2Down(BTNode *root, BTNode *p, BTNode *q) { if (!root || !p || !q) return NULL; if (btExist(root->left, p) && btExist(root->left, q)) { return btLCATop2Down(root->left, p, q); } else if (btExist(root->right, p) && btExist(root->right, q)) { return btLCATop2Down(root->right, p, q); } else { return root; } } /** * 二叉树结点存在性判断 */ int btExist(BTNode *root, BTNode *node) { if (!root) return 0; if (root == node) return 1; return btExist(root->left, node) || btExist(root->right, node); }
解2：自底向上方法
因为自顶向下方法有很多重复的判断，于是有了这个自底向上的方法。自底向上遍历结点，一旦遇到结点等于p 或者 q，则将其向上传递给它的父结点。
父结点会判断它的左右子树是否都包含其中一个结点，如果是，则父结点一定是这两个结点 p 和 q 的 LCA。如果不是，我们向上传递其中的包含结点 p 或者 q 的子结点，或者 NULL(如果左右子树都没有结点p或q)。该方法时间复杂度为O(N)。
/** * 二叉树最低公共祖先结点-自底向上解法 O(N) */ BTNode *btLCADown2Top(BTNode *root, BTNode *p, BTNode *q) { if (!root) return NULL; if (root == p || root == q) return root; BTNode *left = btLCADown2Top(root->left, p, q); BTNode *right = btLCADown2Top(root->right, p, q); if (left && right) return root; // 如果p和q位于不同的子树 return left ? left: right; //p和q在相同的子树，或者p和q不在子树中 }
4.3 二叉树的最大二叉搜索子树
题：找出二叉树中最大的子树，该子树为二叉搜索树。所谓最大的子树就是指结点数目最多的子树。
___10___ / \ _5_ 15 / \ \ 1 8 7 ___10____ / \ _5_ 15 -------- subtree (1) / \ 1 8 _5_ / \ -------- subtree (2) 1 8
根据维基百科对 子树 的定义，一棵二叉树T的子树由T的某个结点和该结点所有的后代构成。也就是说，该题目中，subtree(2) 才是正确的答案，因为 subtree(1) 不包含结点7，不满足子树的定义。
解1：自顶向下解法
最自然的解法是以根结点开始遍历二叉树所有的结点，判定以当前结点为根的子树是否是BST，如果是，则该结点为根的BST就是最大的BST。如果不是，递归调用左右子树，返回其中包含较多结点的子树。
/** * 查找二叉树最大的二叉搜索子树-自顶向下方法 */ BTNode *largestSubBSTTop2Down(BTNode *root, int *bstSize) { if (!root) { *bstSize = 0; return NULL; } if (isBSTEfficient(root, NULL, NULL)) { //以root为根结点的树为BST，则设置结果为root并返回。 *bstSize = btSize(root); return root; } int lmax, rmax; BTNode *leftBST = largestSubBSTTop2Down(root->left, &lmax); //找出左子树中为BST的最大的子树 BTNode *rightBST = largestSubBSTTop2Down(root->right, &rmax); //找出右子树中为BST的最大的子树 *bstSize = lmax > rmax ? lmax : rmax; //设定结点最大数目 BTNode *result = lmax > rmax ? leftBST : rightBST; return result; }
解2：自底向上解法
自顶向下的解法时间复杂度为 O(N^2)，每个结点都要判断是否满足BST的条件，可以用从底向上方法优化。
我们在判断上面结点为根的子树是否是BST之前已经知道底部结点为根的子树是否是BST，因此只要以底部结点为根的子树不是BST，则以它上面结点为根的子树一定不是BST。我们可以记录子树包含的结点数目，然后跟父结点所在的二叉树比较，来求得最大BST子树。
/** * 查找二叉树最大的二叉搜索子树-自底向上方法 */ BTNode *largestSubBSTDown2Top(BTNode *root, int *bstSize) { BTNode *largestBST = NULL; int min, max, maxNodes=0; findLargestSubBST(root, &min, &max, &maxNodes, &largestBST); *bstSize = maxNodes; return largestBST; } /** * 查找最大二叉搜索子树自底向上方法主体函数 * 如果是BST，则返回BST的结点数目，否则返回-1 */ int findLargestSubBST(BTNode *root, int *min, int *max, int *maxNodes, BTNode **largestSubBST) { if (!root) return 0; int isBST = 1; int leftNodes = findLargestSubBST(root->left, min, max, maxNodes, largestSubBST); int currMin = (leftNodes == 0) ? root->value : *min; if (leftNodes == -1 || (leftNodes != 0 && root->value <= *max)) isBST = 0; int rightNodes = findLargestSubBST(root->right, min, max, maxNodes, largestSubBST); int currMax = (rightNodes == 0) ? root->value : *max; if (rightNodes == -1 || (rightNodes != 0 && root->value > *min)) isBST = 0; if (!isBST) return -1; *min = currMin; *max = currMax; int totalNodes = leftNodes + rightNodes + 1; if (totalNodes > *maxNodes) { *maxNodes = totalNodes; *largestSubBST = root; } return totalNodes; }
