【#|力扣-105题 从前序与中序遍历序列构造二叉树（C++）- dfs】题目链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
题目如下：
文章图片
文章图片
/**
* 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& preorder, vector& inorder) {
//前序(根左右)中序(左根右)
if(preorder.size()==0||inorder.size()==0) return nullptr;
//6个参数分别为，前序-前开始-前末尾，中序-中开始-中末尾
return dfs(preorder,0,preorder.size(),inorder,0,inorder.size());
}
TreeNode* dfs(vector& pre,int preBegin,int preEnd,vector& in,int inBegin,int inEnd){
//1、先序
if(preBegin==preEnd) return nullptr;
//空节点int rootval=pre[preBegin];
TreeNode* root=new TreeNode(rootval);
if(preEnd-preBegin==1) return root;
//只有一个节点//2、中序
int index;
for(index=inBegin;
indexleft=dfs(pre,leftpreBegin,leftpreEnd,in,leftinBegin,leftinEnd);
root->right=dfs(pre,rightpreBegin,rightpreEnd,in,rightinBegin,rightinEnd);
return root;
}
};
推荐阅读
- 算法|蓝桥 小明的游戏1 博弈论 nim
- C++|C++-析构函数
- 麦克算法|第12节课 图
- 寒假刷题特辑|【第五章】 C语言之牛客网刷题笔记 【点进来保证让知识充实你一整天】
- 栈和队列|150. 逆波兰表达式求值
- #|Spark优化总结（二）——代码编写
- 笔记|单调栈详解-基于LeetCode的题目
- 笔记|LeetCode每日一题题解（1189. “气球” 的最大数量）
- 笔记|LeetCode每日一题题解（917. 仅仅反转字母-双指针-python和C++）