leetcode105. 从前序与中序遍历序列构造二叉树
程序员文章站
2022-03-09 10:04:18
...
题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
示例
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
思路
前序是根左右,中序是左根右。
前序【3 9 20 15 7】
中序【9 3 15 20 7】
3必定为根节点,在中序中找到3的位置,其前面【9】必为左子树部分,其后面【15 20 7】必为右子树部分。然后分别在左子树和右子树中找根节点,划分左右子树即可。
代码
/**
* 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:
unordered_map<int, int> myMap;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
for (int i = 0; i < n; i++)
myMap[inorder[i]] = i;
return dfs(preorder, inorder, 0, n-1, 0, n-1);
}
TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir){
if (pl > pr) return nullptr;
int index = myMap[preorder[pl]];
int val = preorder[pl];
int len = index-il;
TreeNode* root = new TreeNode(val);
root->left = dfs(preorder, inorder, pl+1, pl+len, il, index-1);
root->right = dfs(preorder, inorder, pl+len+1, pr, index+1, ir);
return root;
}
};
上一篇: layui 下拉框默认选中
推荐阅读
-
牛客网---通过前序遍历序列和中序遍历序列建立二叉树
-
树与二叉树 树二叉树前序、中序、后序遍历先根遍历后根遍历
-
从前序与中序遍历序列构造二叉树-二叉树
-
java实现二叉树的前序、中序、后序、层次遍历,递归与非递归
-
LeetCode 105. 从前序与中序遍历序列构造二叉树(各种遍历二叉树的性质,递归建树)
-
LeetCode 106. 从中序与后序遍历序列构造二叉树(二叉树基础之树的重建)
-
二叉树前序、中序、后序、层序遍历的递归与非递归java实现
-
java实现 二叉树的构造、前序遍历、中序遍历、后续遍历、广度遍历、 三叉链表
-
从中序与后序遍历序列构造二叉树
-
【树】B022_从中序与后序遍历序列构造二叉树(递归)