面试题07：重建二叉树（C++）

题目地址：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

题目示例

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

3
/
9 20
/
15 7

解题思路

递归+分治思想

先序遍历规则：根节点==》左子树==》右子树

中序遍历规则：左子树==》根节点==》右子树

1.  假设先序序列preorder中的第一个字母(根节点root)在先序序列数组中的位置为p_start，最后一个字母在该数组中的位置为p_end；中序序列inorder中的第一个字母在中序序列数组中的位置为i_start，最后一个字母在中序序列数组中的位置为i_end。
2. 然后，在中序序列inorder中找到根节点对应的下标root_index，而该下标将中序序列分为左右子树两部分，我们假设根节点在中序序列的i位置，则左子树的节点个数left_len = i - i_start，接下来，在先序遍历序列preorder中找到左子树序列，即[p_start + 1, p_start + left_len]，右子树序列为[p_start + left_len + 1, p_end]，而在中序遍历序列inorder中左子树序列为[i_start, i - 1]，右子树序列为[i + 1, i_end]。
3. 最后，左右子树递归调用二叉树构造函数，递归临界条件是先序序列preorder中元素为0时结束构造。

分析题目可知，二叉树中的节点值均是唯一的，不存在重复值。所以，我们可以利用二叉树先序遍历和中序遍历特点，完成如下的工作：

• Step1：确定根节点，即先序遍历preorder中的首个节点；
• Step2：在中序遍历inorder中找到根节点的索引值index，以此为界，将中序遍历序列划分为【左子树，根节点，右子树】，其中，左子树为索引值0至index-1，即inorder[0:index-1]，右子树为index+1至中序遍历末尾元素，即inorder[index+1:]；
• Step3：根据中序遍历序列中左右子树的节点数量leftLen，将先序遍历序列划分为【根节点，左子树，右子树】，其中，左子树为索引值1至leftLen，即preorder[1:leftLen]，右子树为leftLen+1至先序遍历末尾元素，即preorder[leftLen+1:]；
• Step4：分别利用先序遍历和中序遍历中的左子树递归构造二叉树的左子树，先序遍历和中序遍历中的右子树递归构造二叉树的右子树

程序源码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0 || inorder.size() == 0) return nullptr;
        return build_tree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
       
    }
    TreeNode* build_tree(vector<int> preorder, int p_start, int p_end, vector<int> inorder, int i_start, int i_end)
    {
        TreeNode* root = new TreeNode(preorder[p_start]); //根据先序数组获取根节点
        int root_index = i_start; //初始化中序数组下标，便于计算左右子树长度
        while(inorder[root_index] != preorder[p_start]) root_index++; //中序数组中查找根节点所在下标
        int left_len = root_index - i_start; //左子树长度
        int right_len = i_end - root_index; //右子树长度

        if(left_len > 0) root->left = build_tree(preorder, p_start + 1, p_start + left_len, inorder, i_start, root_index - 1);
        if(right_len > 0) root->right = build_tree(preorder,p_start + left_len + 1, p_end, inorder, root_index + 1, i_end);
        return root;

    }
};

简化代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0 || inorder.size() == 0) return NULL;
        TreeNode* treeNode = new TreeNode(preorder[0]);
        int index = distance(begin(inorder), find(inorder.begin(), inorder.end(), preorder[0]));
        vector<int> left_preorder(preorder.begin() + 1, preorder.begin() + index + 1);
        vector<int> right_preorder(preorder.begin() + index + 1, preorder.end());
        vector<int> left_inorder(inorder.begin(), inorder.begin() + index);
        vector<int> right_inorder(inorder.begin() + index + 1, inorder.end());
        treeNode->left = buildTree(left_preorder, left_inorder);
        treeNode->right = buildTree(right_preorder, right_inorder);
        return treeNode;
    }
};