Leetcode剑指offer——面试题07. 重建二叉树
程序员文章站
2022-06-17 17:03:45
...
这个题可以用递归的思想来做。首先先序遍历的头节点就是根节点,从中序遍历中找到根节点,根节点左边为左子树,右边为右子树,左子树的根节点为先序遍历的根节点索引+1,右子树的根节点为线序遍历的根节点索引+中序遍历根节点索引-中序遍历开始的索引+1.返回条件为中序遍历开始的索引>结束的索引。
/**
* 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:
vector<int> prenums;
unordered_map<int,int> umap;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
{
prenums=preorder;
int length=preorder.size();
for(int i=0;i<length;i++)
{
umap.insert(make_pair(inorder[i],i));
}
return buildTree(0,0,length-1);
}
TreeNode* buildTree(int pre_order,int in_head,int in_rear)
{
if(in_head>in_rear)
{
return NULL;
}
TreeNode* tr=new TreeNode(prenums[pre_order]);
auto i =umap.find(prenums[pre_order]);
int j=i->second;
tr->left=buildTree(pre_order+1,in_head,j-1);
tr->right=buildTree(pre_order+j-in_head+1,j+1,in_rear);
return tr;
}
};
推荐阅读
-
《剑指offer》面试题6 重建二叉树
-
《剑指offer》面试题6 重建二叉树
-
剑指 Offer 07. 重建二叉树——【前中序】和【中后序】重建二叉树的递归思路详解
-
leetcode 160剑指offer面试题52. 两个链表的第一个公共节点(python3)
-
leetcode 面试题32 (剑指offer)- II. 从上到下打印二叉树 II(python3)
-
leetcode 113 剑指offer 面试题34. 二叉树中和为某一值的路径(python3)
-
剑指offer-重建二叉树
-
剑指offer——面试题62:序列化二叉树
-
剑指offer 面试题62 序列化和反序列化二叉树
-
【剑指Offer】面试题62:序列化二叉树