写在前面：
今天的每日一题好难，我不会dp啊啊啊啊啊啊。
所以，我又来刷剑指 Offer 啦。
题目：剑指 Offer 07. 重建二叉树 - 力扣（Leetcode）
题目的接口：
/** * 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& preorder, vector& inorder) { } };
解题思路：
这道题不太简单啊，我得想法是：
通过前序遍历的特性找来确定根节点，
然后对应到中序遍历上，再由中序遍历通过递归的方式重建二叉树。
具体如下：
我们建一个字函数来递归，
设置下标prei 访问前序遍历数组，
使用inbegin和inend确定中序遍历的区间，
然后开展递归。
代码：
/** * 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: //prei走一步少一个节点，需要传引用修改他的值 TreeNode* _buildTree(vector& preorder, vector& inorder, int& prei, int inbegin, int inend) { //当分出来的中序区间走完（不合法），返回空指针 //证明该节点没有左/右孩子了 if(inbegin > inend) { return nullptr; } //将我们要返回的根节点new出来（毕竟要重建二叉树，当然要根节点） TreeNode*root = new TreeNode(preorder[prei]); //让rooti从中序区间开头开始，找出这个区间对应的根节点 int rooti = inbegin; //遍历中序区间 while(rooti <= inend) { //如果找到根节点就跳出循环 if(inorder[rooti] == preorder[prei]) { break; } rooti++; } //找到根节点后，访问前序遍历数组prei++ prei++; //接下来就是依次根据当前的根节点，分成左右区间进行递归 //[inbegin, rooti - 1] rooti [rooti + 1, inend] //函数的最后两个参数就是区间的头和尾了 root->left = _buildTree(preorder, inorder, prei, inbegin, rooti - 1); root->right = _buildTree(preorder, inorder, prei, rooti + 1, inend); //最后返回树的根 return root; } TreeNode* buildTree(vector& preorder, vector& inorder) { //设置访问前序遍历的下标，走完前序就走完整个二叉树了 int prei = 0; //创建子函数，将中序遍历的区间传过去 return _buildTree(preorder, inorder, prei, 0, inorder.size()-1); } };
过啦！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
