【剑指offer】重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解题思路

给出遍历序列唯一确定二叉树有两种方式：

1. 前序遍历 + 中序遍历
2. 后序遍历 + 中序遍历

这道题中给出了前序遍历序列和中序遍历序列，要求重建二叉树。

我们知道前序遍历的顺序是：根->左->右，而中序遍历的顺序是：左->根->右。以题目给出的例子，简单分析一下。

前序遍历序列的第一项是 “1”，是树的根结点，对应中序遍历序列的第 4 项，即 vin[3]。可知，中序遍历中，“1” 左侧的都是根结点 “1” 的左子树结点，而 “1” 右侧的都是根结点 “1” 的右子树结点。

同样地，我们看前序遍历序列的第二项 “2”。在中序遍历序列中 “2” 的左侧有 “4” 和 “7”，说明这两个都是结点 “2” 的左子树孩子，而 “2” 的后侧除了根节点 “1”，没有其他数，说明 “2” 没有右子树。

简单地画了个图，上面是前序遍历序列，下面是中序遍历序列。中序遍历序列中结点 “1” 上面分析过，不重复了。同样地，根结点 “3” 在中序遍历序列中，在它左侧的除了它的父结点以外的数，都是它的左子树结点数值；而在它后侧的都是它的右子树结点。

分析完重建原理后，考虑到这是树，最常用的方法是递归。采用递归的方法实现，就需要找到递归的两个要素。按照上述分析，我们知道，首先找到 “根结点” 在中序遍历序列中的位置，然后就可以划分这个 “根结点” 的左右子树结点。左右子树结点分别对应着两个“缩短”了的序列，然后又继续找 “根节点” 划分左右子树结点，如此类推，直至这个 “根结点” 没有左右子树，说明到达叶子结点。所以递归结束条件就是当前序或者中序遍历序列被缩短到没有了，就返回 NULL，表示所有结点都建立好了。递归公式则是找到 “根节点”，然后构建左、右子树。

实现代码：

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.empty()&&vin.empty()) return NULL; // 一个空另一个非空 报错
        return constructNode(pre,0,pre.size()-1,vin,0,vin.size()-1);
    }
    TreeNode* constructNode(vector<int> pre,int startPre,int endPre,vector<int> in, int startIn, int endIn){
        if(startPre>endPre || startIn>endIn){
            return NULL;
        }
        TreeNode* root = new TreeNode(pre[startPre]);
        for(int i=startIn;i<=endIn;i++){
            if(in[i]==pre[startPre]){
                root->left = constructNode(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
                root->right = constructNode(pre,startPre+i-startIn+1,endPre,in,i+1,endIn);
                break;
            }
        }
        return root;
    }
};

参考链接：
1.https://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6?f=discussion