leetcode105. 从前序与中序遍历序列构造二叉树，步骤详解附代码

leetcode105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]

算法思路

前序遍历特性：在前序遍历中，第一个元素总是根节点。
中序遍历特性：在中序遍历中，根节点将序列分为左子树和右子树。

具体算法步骤

检查空序列：如果前序序列为空，返回 NULL 表示没有树。

创建根节点：使用前序遍历的第一个元素作为根节点的值，并创建相应的 TreeNode 对象。

确定根节点在中序遍历中的位置：通过遍历中序序列找到根节点的位置，这个位置将中序序列分为左子树和右子树。

划分左右子树的前序和中序序列：根据根节点在中序序列中的位置，划分出左子树和右子树的前序和中序序列。

递归构建子树：对左子树和右子树的序列递归调用 traversal 函数来构建子树，并将结果分别赋给根节点的左右子节点。

返回根节点：完成子树构建后，返回根节点，这样就完成了整棵树的构建。

这里有个注意的点，就是我们先确定中序遍历的数组内容，再确定先序遍历的数组内容，这样的好处是我们可以根据中序数组的长度来确定先序遍历的数组。如果反过来的话会很麻烦，读者可以自己试试。
具体来说
划分左右子树：
在中序遍历中，根节点左边的元素构成左子树，右边的元素构成右子树。因此，我们可以通过 del 来划分左右子树的中序遍历序列：
leftInorder 包含了根节点左边的所有元素。
rightInorder 包含了根节点右边的所有元素。

确定前序遍历中的左右子树序列：
前序遍历中，根节点后面的元素按照左子树和右子树的顺序排列。因此，我们可以根据 leftInorder 的大小来确定左子树在前序遍历中的序列：
leftPreorder 包含了左子树的所有前序遍历元素。
同理，右子树的前序遍历序列 rightPreorder 可以通过 leftInorder.size() 来确定起始位置。

具体代码

class Solution {
public:
    TreeNode* traversal(vector<int>& preorder,vector<int>& inorder)
    {
        if(preorder.size()==0) return NULL;
        int rootValue=preorder[0];
        TreeNode* root=new TreeNode(rootValue);
        if(preorder.size()==1) return root;
        int del;
        for(del=0;del<inorder.size();del++)
        {
            if(inorder[del]==rootValue) break;
        }
        vector<int> leftInorder(inorder.begin(),inorder.begin()+del);
        vector<int> rightInorder(inorder.begin()+del+1,inorder.end());
        vector<int> leftPreorder(preorder.begin()+1,preorder.begin()+1+leftInorder.size());
        vector<int> rightPreorder(preorder.begin()+1+leftInorder.size(),preorder.end());
        root->left=traversal(leftPreorder,leftInorder);
        root->right=traversal(rightPreorder,rightInorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
     if(inorder.size()==0 || preorder.size()==0) return NULL;
     return traversal(preorder,inorder);
    }
};

做完此题，可以看看姊妹题

需要注意的是，只有中序与前序、中序与后序才能确定唯一的二叉树，前序和后序无法确定唯一的二叉树！