LeetCode-105-前序和中序构建二叉树

给定一个二叉树前序遍历数组A 124367,中序遍历得到数组B, 421637。我们的任务是从这两个结果中构造出原来二叉树。

根据前序遍历的顺序,可以知道数组是先存放根,然后是左子树,最后是右子树。

根据中序遍历的顺序,可以知道数组是先放左子树,然后是根,最后是右子树。

根据定义,前序遍历数组第一个位置是根节点,但左子树和右子树大小未知。而中序遍历一旦确定根的位置,就可以确定左右子树的大小。这两者刚好是互补关系。

因此具体过程是

  • 用前序数组的第一个位置确定中序数组的根位置
  • 将中序数组分成两个部分,得到左右子树的大小。
  • 用左右子树的大小确定前序数组的左右子树位置
  • 对于新生成的左右子树,用上面方法确定新的根位置和左右子树大小。

对于本问题,就是1将421637分成42和637,这意味着左子数大小为2,右子数大小为3.于是124367被分成1,24,367.

24和42是新的左子树问题,367和637是新的右子树问题。

理清思路之后,我们可以按照递归模版四步走起来

第零步:思考函数名和传递的参数和全局变量。根据我们的分析,我们最重要的就是子问题对应数组的区间,也就是我们需要记录前序数组的左右子树开始和结束(pb, pe), 中序数组的开始和结束(ib, ie), 函数名的话,就写dc吧

第一步:终止条件。这里终止条件是前序数组用完了(当然中序数组肯定也用完了)

if (pb > pe) return NULL;

第二步: 处理逻辑。每次用前序节点的第一个位置构建根节点,然后拆分中序节点,获取左右子树的大小,

TreeNode *root = new TreeNode(preorder[pb]);
int rootIndex = mp[root->val]; //获取中序的位置
int leftSize = rootIndex - ib; //左子树大小
int rightSize = ie - rootIndex; //右

第三步,下潜一层, 新的一层要带新的参数过去。

root->left = dc(preorder,pb+1,pb+leftSize, inorder,ib, rootIndex-1);
root->right = dc(preorder,pb+leftSize+1, pe, inorder, rootIndex+1, ie);

第四步:状态重置。此处不需要

最终返回root即可。

对应的完成代码见 https://github.com/xuzhougeng/algorithm006-class01/blob/master/Week_02/G20200343030533/LeetCode_105_533.cpp

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×