题目描述

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

初始代码

/**
 * 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) {

    }
};

解法1

碰到数的前序, 中序和后序遍历相关的题目, 其实心里是有一点点怕的. 因为这类型的代码写的比较少.
但其实树的构造过程还是有套路可循的.

• 首先, 构造一棵树, 一般是从树的根结点开始. 首先创建一个根结点.
• 分别构造根结点的左子树和右子树. 由于树的定义本身就具有递归性, 因此使用递归来构造根结点的左右子树也就显得顺理成章了.

针对本题, 需要理解前序遍历序列的元素特点: 首元素总是根结点. 但是通过前序遍历序列无法确定根结点的左子树有哪些元素, 右子树又有哪些元素.
而结合中序遍历序列, 就可以解决上面的问题. 在中序遍历序列中找到根结点的位置, 然后根结点位置左侧的元素就是要构造的树的根结点的左子树所包含的所有元素(保存到vin_left中), 而根结点位置右侧的元素则是要构造的树的根结点的右子树所包含的所有元素(保存到vin_right中).

根据上面的分析结果, 我们接着从前序遍历序列中分解出左子树所含元素的子区间pre_left, 以及右子树所含元素的子区间pre_right.

利用pre_left和vin_left, 可以递归地构造根结点的左子树.
利用pre_right和vin_right, 可以递归地构造根结点的右子树.

下面是实现代码:

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size() == 0) return NULL; // 序列为空, 即空树
        if(pre.size() == 1) { //序列中只有一个元素, 即是叶子节点
            return new TreeNode(pre.at(0)); 
        }

        TreeNode *root = new TreeNode(pre.at(0)); //前序遍历序列的首元素总是树的根结点
        int m;
        for(m=0; m<vin.size(); m++){ //在中序遍历序列中找到根结点的位置
            if(vin.at(m) == root->val){
                break;
            }
        }
        // assert(m < vin.size()); // 总是找得到的, 且是唯一的(根据题意).

        //使用vector的拷贝构造函数来分别得到递归调用时需要用到的四个vector区间
        vector<int> pre_left(pre.begin()+1, pre.begin()+m+1);
        vector<int> pre_right(pre.begin()+m+1, pre.end());
        vector<int> vin_left(vin.begin(), vin.begin()+m);
        vector<int> vin_right(vin.begin()+m+1, vin.end());

        // 递归构造左子树和右子树
        root->left = reConstructBinaryTree(pre_left, vin_left);
        root->right = reConstructBinaryTree(pre_right, vin_right);

        return root;
    }
};

代码实现中使用到的一些细节:

• 递归的出口1: 要考虑到pre和vin本身为空的情况, 因此加入了当pre.size()==0时返回NULL的条件判断.
• 递归的出口2: 只要pre和vin非空, 那么递归的出口就都是从出口2返回的, 即最多执行到叶子结点.
• 通过拷贝构造函数来依次得到四个子区间vector, 避免了自己写循环向每个vector中插入元素的麻烦