LeetCode Hot100 | Day6 | 从前序和中序数组构建二叉树

LeetCode Hot100 | Day6 | 从前序和中序数组构建二叉树

从前序和中序数组构建二叉树

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

class Solution {
public:TreeNode *tra(vector<int> preorder, vector<int> inorder){if(preorder.size()==0)return nullptr;int val=preorder[0];TreeNode* t=new TreeNode (val);int index=0;for(index=0;index<inorder.size();index++)if(val==inorder[index])break;t->left=tra(vector<int>(preorder.begin()+1,preorder.begin()+1+index),vector<int>(inorder.begin(),inorder.begin()+index));t->right=tra(vector<int>(preorder.begin()+1+index,preorder.end()),vector<int>(inorder.begin()+index+1,inorder.end()));return t;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return tra(preorder,inorder);}
};

读者可以参考这篇博客来学习本题解法，思路都一样

代码随想录 | Day25 | 二叉树：从中序与后序遍历构造二叉树&&最大二叉树-CSDN博客

注意点：切割子树的前序和中序区间的时候要注意使用的区间要统一

前闭后开就全都前闭后开

前开后闭就全都前开后闭