树和二叉树_6

一、leetcode-105

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

样例输入：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

样例输出： [3,9,20,null,null,15,7]

二、题解

1.引库

 #include <iostream>
 #include <cstdio>
 #include <cstdlib>
 #include <queue>
 #include <stack>
 #include <algorithm>
 #include <string>
 #include <map>
 #include <set>
 #include <vector>
 using namespace std;
 

2.代码

/**
 * 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) {
        if(preorder.size()==0) return NULL;
        int pos=0,n=preorder.size();
        while(inorder[pos]!=preorder[0]) pos++;
        TreeNode *root=new TreeNode(preorder[0]);
        vector<int> preArr,inArr;
        for(int i=1;i<=pos;i++) preArr.push_back(preorder[i]);
        for(int i=0;i<pos;i++) inArr.push_back(inorder[i]);
        root->left=buildTree(preArr,inArr);
        preArr.clear(),inArr.clear();
        for(int i=pos+1;i<n;i++) preArr.push_back(preorder[i]);
        for(int i=pos+1;i<n;i++) inArr.push_back(inorder[i]);
        root->right=buildTree(preArr,inArr);
        return root;
    }
};