Leetcode105. 从前序与中序遍历序列构造二叉树
程序员文章站
2022-03-09 10:04:00
...
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3 / \ 9 20 / \ 15 7
简析:主要是通过前序和中序来构造树,也是用递归的方法,选定各个节点,对剩余的数据进行再构造。直到输出为NULL结束。
/**
* 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* dfs(vector<int>& preorder, vector<int>& inorder,int pre,int inl,int inr)
{
if(inl == inr) return new TreeNode(preorder[pre]);
if(inl > inr) return NULL;
TreeNode* root = new TreeNode(preorder[pre]);
int i = inl;
while(preorder[pre] != inorder[i] && i <= inr) i++;
root->left = dfs(preorder,inorder,pre+1,inl,i-1);
root->right = dfs(preorder,inorder,pre+i-inl+1,i+1,inr);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int r = preorder.size()-1;
return dfs(preorder,inorder,0,0,r);
}
};
下一篇: layui 下拉框默认选中
推荐阅读
-
牛客网---通过前序遍历序列和中序遍历序列建立二叉树
-
树与二叉树 树二叉树前序、中序、后序遍历先根遍历后根遍历
-
从前序与中序遍历序列构造二叉树-二叉树
-
java实现二叉树的前序、中序、后序、层次遍历,递归与非递归
-
LeetCode 105. 从前序与中序遍历序列构造二叉树(各种遍历二叉树的性质,递归建树)
-
LeetCode 106. 从中序与后序遍历序列构造二叉树(二叉树基础之树的重建)
-
二叉树前序、中序、后序、层序遍历的递归与非递归java实现
-
java实现 二叉树的构造、前序遍历、中序遍历、后续遍历、广度遍历、 三叉链表
-
从中序与后序遍历序列构造二叉树
-
【树】B022_从中序与后序遍历序列构造二叉树(递归)