题目：重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历结果中都不含重复的数字。例如输入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列 {4,7,2,1,5,3,8,6} ，则重建如图二叉树并输出它的头节点。
二叉树的定义如下：
1
2
3
4
5
6
| struct BinaryTreeNode{
int val;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(int x):val(x),left(NULL),right(NULL){}
};
|
解析
二叉树定义：每个节点最多只能有两个子节点的树。又分为
- 最大堆：根节点值最大
- 最小堆：根节点值最小
- 搜索树：左子节点值小于或等于根节点值，右子节点值大于或等于根节点值
- 红黑树：任意节点的左右子树中最长路径的长度不会超过最短路径的两倍
二叉树的遍历方式分为
- 前序遍历：根节点->左子节点->右子节点
- 中序遍历：左子节点->根节点->右子节点
- 后序遍历：左子节点->右子节点->根节点
- 层序遍历(广度优先遍历)：从根到叶分层，每层从左到右遍历
小诀窍：中序遍历可由投影法直观得出。如图所示
对于题中二叉树不难得出
- 前序遍历为
10 6 4 8 14 12 16
- 中序遍历为
4 6 8 10 12 14 16
- 后序遍历为
4 8 6 12 16 14 10
观察发现
- 前序遍历顺序记录根节点信息，即根节点
10 先于子节点 6 14 遍历
- 中序遍历记录左右子树范围，即左子树节点
4 6 8 先于根节点 10 遍历，右子树节点 12 14 16 后于根节点 10 遍历
- 后序遍历倒序记录根节点信息，即根节点
10 后于子节点 6 14 遍历
以前序为主，中序为辅，便可重建二叉树😎。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| BinaryTreeNode* rebuildBinaryTree(int *preOrder, int *inOrder, int length)
{
if (nullptr == preOrder || nullptr == inOrder || length <= 0)
return nullptr;
BinaryTreeNode *pRoot = nullptr;
BinaryTreeNode *pNode = nullptr;
for (int i = 0; i < length; ++i)
if (nullptr != pRoot)
{
bool leftNode = false;
int position = length;
for (int j = 0; j < length; ++j)
if (inOrder[j] == pNode->val)
position = j;
else if (inOrder[j] == preOrder[i])
{
leftNode = j < position;
break;
}
if (leftNode)
{
pNode->left = new BinaryTreeNode(preOrder[i]);
pNode = pNode->left;
}
else
{
pNode->right = new BinaryTreeNode(preOrder[i]);
pNode = pNode->right;
}
}
else
pNode = pRoot = new BinaryTreeNode(preOrder[i]);
return pRoot;
}
|
此法使用双重循环，效率甚低。可以使用map将inOrder中的数值对应下标存储，以空间换时间。
不过书中提供了更好的思路（分治法）：既然可得出左右子树包含数值，不妨继续对子树继续进行左右子树划分，由此可先（解决小问题）得出含叶子节点子树，继而（解决大问题）合并子树成较大子树，最终形成二叉树。下为子树分析图片
分治法需递归实现，书中神级代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| BinaryTreeNode* rebuildBinaryTree(int *preOrder, int *inOrder, int length)
{
if (nullptr == preOrder || nullptr == inOrder || length <= 0)
return nullptr;
return constructCore(preOrder, preOrder + length - 1, inOrder, inOrder + length - 1);
}
BinaryTreeNode* constructCore(int *startPreOrder, int *endPreOrder, int *startInOrder, int *endInOrder)
{
BinaryTreeNode * pRoot = new BinaryTreeNode(*startPreOrder);
if (startPreOrder == endPreOrder)
if (startInOrder == endInOrder)
if (*startPreOrder == *startInOrder)
return pRoot;
else
throw std::exception("Invalid input");
int * rootPosition = startInOrder;
while (*rootPosition != *startPreOrder && rootPosition <= endInOrder)
++rootPosition;
if (rootPosition > endInOrder)
throw std::exception("Invalid input");
int leftLength = (rootPosition - 1) - startInOrder;
int rightLength = endInOrder - (rootPosition + 1);
if (leftLength > 0)
pRoot->left = constructCore(startPreOrder + 1, (startPreOrder + 1) + leftLength, startInOrder, rootPosition - 1);
if (rightLength > 0)
pRoot->right = constructCore((startPreOrder + 1) + leftLength + 1, endPreOrder, rootPosition + 1, endInOrder);
return pRoot;
}
|
本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可
