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

题目描述

  根据一棵树的前序遍历与中序遍历构造二叉树。注意：你可以假设树中没有重复的元素。

输入输出样例

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回的二叉树如下：

  3
 / \
9  20
  /  \
 15   7

题解

  本题是通过中序与前序构造二叉树，那么我们就需要想一想它们是什么如何遍历的？根据它们遍历的顺序，导致了preorder与inorder具有不同的分布特点。具体如下:

  根据它我们可以先将伪代码大致的写出来：

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return create(preorder,0,preorder.size()-1,
                      inorder,0,inorder.size()-1);
    }
    TreeNode* create(vector<int>& preorder,int preStart,int preEnd,
                    vector<int>&inorder,int inStart,int inEnd)
    {
        int rootval = preorder[preStart];
        int index = 0;

        for (int i = inStart; i <= inEnd; i++) {
            if (rootval == inorder[i]) {
                index = i;
                break;
            }
        }
		TreeNode* root = new TreeNode(rootval);

        root->left = create(preorder,?,?,
                            inorder,?,?);
        root->right = create(preorder,?,?,
                            inorder,?,?);
        return root;
    }
};

  接下来我们就仅需要确定这个递归的区间就可以了，对于上图我们还可以再进行细分一下。中序遍历清晰的提供了左右子树，前序遍历提供了根节点。那么对于前序来说，去除根节点就是我们需要的左子树节点了。那么我们通过中序获取左右子树的长度，由于树的长度都相同的，不同之处仅在于分布。因此，我们对前序进行一定的加减操作，就可以获得对应的前序的左右子树的位置了。具体代码如下所示：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return create(preorder,0,preorder.size()-1,
                      inorder,0,inorder.size()-1);
    }
    TreeNode* create(vector<int>& preorder,int preStart,int preEnd,
                    vector<int>&inorder,int inStart,int inEnd)
    {
        if (preStart > preEnd) return nullptr;
        int rootval = preorder[preStart];
        int index = 0;

        for (int i = inStart; i <= inEnd; i++) {
            if (rootval == inorder[i]) {
                index = i;
                break;
            }
        }
		int leftsize = index - inStart;

        TreeNode* root = new TreeNode(rootval);

        root->left = create(preorder,preStart+1,preStart+leftsize,
                            inorder,inStart,index-1);
        root->right = create(preorder,preStart+leftsize+1,preEnd,
                            inorder,index+1,inEnd);
        return root;
    }
};