数据结构与算法

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吧

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

1
if (pb > pe) return NULL;

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

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

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

1
2
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