原题传送门—>>

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

For example, given

  • preorder = [3,9,20,15,7]
  • inorder = [9,3,15,20,7]

  • Return the following binary tree:

  • 3

  • / \
  • 9 20
  • / \
  • 15 7
/**
 * 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) {
     //1 根据先序遍历确定根节点，再在中序遍历中找到该节点
        if(preorder.empty())
            return NULL;
        int leftSize = find(inorder.begin(), inorder.end(), preorder.front()) - inorder.begin();//左子树长度
        TreeNode* base = new TreeNode(preorder.front());
        vector<int> leftPreorder(preorder.begin()+1, preorder.begin()+1+leftSize);//左子树的先序遍历序列
        vector<int> leftInorder(inorder.begin(), inorder.begin()+leftSize);//左子树的中序遍历序列
        vector<int> rightPreorder(preorder.begin()+1+leftSize, preorder.end());//右子树的先序遍历序列
        vector<int> rightInorder(inorder.begin()+1+leftSize, inorder.end());//右子树的中序遍历序列
        base->left = buildTree(leftPreorder,leftInorder);
        base->right = buildTree(rightPreorder, rightInorder);
        return base;
    }
};

tip: 临时变量不可作为引用类型参数的实参。
比如这句代码：

  • base->left = buildTree(leftPreorder,leftInorder);
    我一开始其实是写成
  • base->left = buildTree(vector(preorder.begin()+1, preorder.begin()+1+leftSize),leftInorder(inorder.begin(), inorder.begin()+leftSize));

这样是会报错的。