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

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

思路🧐：

  由题，前序可以知道根，中序能知道左右子树，那么我们可以进行第一次判断——根为3，左子树为9，右子树为15,20,7。可以利用递归，进行每个结点的判定，比如右子树为15,20,7，而前序顺序为20,15,7，所以可以判断右子树根为20，再一次用中序得出左子树为15，右子树为7，以此类推…

  我们可以用rooti(中序数组下标)来切割左右子树，rooti-1的范围是左子树，rooti+1的范围是右子树，rooti为需要构建的二叉树结点，前序用于找根，中序用于划分，由此反复递归直到整棵树遍历完，就能够构造一颗二叉树了。

代码🔎：

class Solution {
public:TreeNode* _build(vector<int>& preorder, vector<int>& inorder, int& previ, int inbegin,int inend){if(inbegin > inend)return nullptr;int rooti = inbegin; //划分下标while(rooti <= inend){//当[rooti]==[previ]，表示找到根了if(preorder[previ] == inorder[rooti]) {break;}rooti++; //没找到就++}//构建结点，并且++前序结点，方便下次rooti划分TreeNode* root = new TreeNode(preorder[previ++]);//左子树范围在[begin,root-1]root->left = _build(preorder, inorder, previ, inbegin, rooti - 1);//右子树范围在[root+1,end]root->right = _build(preorder, inorder, previ, rooti + 1, inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i = 0;TreeNode* root = _build(preorder,inorder, i, 0, inorder.size() - 1);return root;}
};