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

雨点打透心脏的1/2处 2024-03-16 13:49 22阅读 0赞

>  作者：小卢
> 
> 专栏：《Leetcode》
> 
> 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
> 
> ![7d63d497b5114103b3dd7633a1ba4731.jpeg][]
> 
> --------------------

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

[力扣][Link 1]

题目描述：

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

示例：

![c447d6d7a147489a9cebd446cdcd8ced.png][]

思路：

利用previ去变量前序数组找到根的位置，然后再去中序数组里面找到根，分割左右子树区间

然后begin和end在中序数组去分割左右子树，然后利用递归构建树

代码：

class Solution {
    public:
        TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int&previ,int begin,int end) {
            if(begin>end)
            return nullptr;
            TreeNode*root=new TreeNode(preorder[previ]);
            int rooti=0;
            while(preorder[previ]!=inorder[rooti])
            {
                rooti++;
            }
            previ++;
            root->left=_buildTree(preorder,inorder,previ,begin,rooti-1);
            root->right=_buildTree(preorder,inorder,previ,rooti+1,end);
            return root;
    }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            int i=0;
            return _buildTree(preorder,inorder,i,0,inorder.size()-1);
        }
    
    };

[7d63d497b5114103b3dd7633a1ba4731.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/34bc8cfd9f9041f4912bfa26082385fa.png
[Link 1]: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[c447d6d7a147489a9cebd446cdcd8ced.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/f72d515fa1e948c0b2bc764f932c7536.png