LeetCode 原题链接
- Construct Binary Tree from Inorder and Postorder Traversal - LeetCode
- Construct Binary Tree from Preorder and Postorder Traversal - LeetCode
题目大意
- 给定一棵二叉树的中序遍历和后序遍历,求这棵二叉树的结构。
- 给定一棵二叉树的前序遍历和中序遍历,求这棵二叉树的结构。
样例
Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]
Output: [3, 9, 20, null, null, 15, 7]Input: preorder = [3, 9, 20, 15, 7], postorder = [9, 3, 15, 20, 7]
Output: [3, 9, 20, null, null, 15, 7]
解题思路
这两题的解题思路类似,主要应用了二叉树的这样一个结论:
对于任意一棵二叉树:
- 其前序遍历序列的第一个元素为该树的根
- 其后序遍历序列的最后一个元素为该树的根
然后对于一棵二叉树的遍历序列,其元素排布总是遵循如下规律:
- 前序遍历:
[根元素, [左子树元素], [右子树元素]]
- 中序遍历:
[[左子树元素], 根元素, [右子树元素]]
- 后序遍历:
[[左子树元素], [右子树元素], 根元素]
有了以上结论,这两题的思路就很明确了:先从前序(或后序)遍历中找到根元素,然后将遍历结果按照上面的元素分布规律分成三个部分,对于左子树和右子树,递归地调用该算法去构建,即可得出完整的结构。
根据以上思路,可以写出对数组进行分割的代码,记录如下:
-
前序遍历:
/// <summary>
/// 把二叉树的前序遍历序列分拆成左右两部分
/// 左右两部分中,若有一个部分不存在,则返回长度为 0 的数组
///
/// 在调用该方法前,需要提前为左右两部分的数组分配空间(即需要左右子树的序列大小)
/// </summary>
/// <param name="sourceArray">一个数组,表示二叉树的前序遍历序列</param>
/// <param name="leftPart">一个数组,表示这棵树的左子树的前序遍历序列</param>
/// <param name="rightPart">一个数组,表示这棵树的右子树的前序遍历序列</param>
private void SplitArray(int[] sourceArray, int[] leftPart, int[] rightPart)
{
// 对于前序遍历,各部分对应的下标范围为:
// - [0, 1):根节点
// - [1, 1 + leftPart.Length):左子树的前序遍历序列
// - [1 + leftPart.Length, sourceArray.Length):右子树的遍历序列 // 复制左子树内容
Array.Copy(sourceArray, 1, leftPart, 0, leftPart.Length);
// 复制右子树内容
Array.Copy(sourceArray, 1 + leftPart.Length, rightPart, 0, rightPart.Length);
} -
中序遍历:
/// <summary>
/// 把二叉树的中序遍历序列分拆成左右两部分
/// 左右两部分中,若有一个部分不存在,则返回长度为 0 的数组
/// </summary>
/// <param name="sourceArray">一个数组,表示二叉树的中序遍历序列</param>
/// <param name="splitIndex">这棵二叉树的根节点,在中序遍历序列中的下标</param>
/// <param name="leftPart">输出参数,表示这棵树的左子树的中序遍历序列</param>
/// <param name="rightPart">输出参数,表示这棵树的右子树的中序遍历序列</param>
void SplitArray(int[] sourceArray, int splitIndex, out int[] leftPart, out int[] rightPart)
{
// 为左右两部分分配空间
// 对于中序遍历,各部分对应的下标范围为
// - [0, splitIndex):左子树的中序遍历序列
// - [splitIndex, splitIndex + 1):根节点
// - [splitIndex + 1, sourceArray.Length):右子树的中序遍历序列
leftPart = new int[splitIndex];
rightPart = new int[sourceArray.Length - (splitIndex + 1)]; // 复制左子树内容
Array.Copy(sourceArray, leftPart, leftPart.Length); // 复制右子树内容
Array.Copy(sourceArray, splitIndex + 1, rightPart, 0, rightPart.Length);
} -
后序遍历:
/// <summary>
/// 把二叉树的后序遍历序列分拆成左右两部分
/// 左右两部分中,若有一个部分不存在,则返回长度为 0 的数组
///
/// 在调用该方法前,需要提前为左右两部分的数组分配空间(即需要左右子树的序列大小)
/// </summary>
/// <param name="sourceArray">一个数组,表示二叉树的后序遍历序列</param>
/// <param name="leftPart">一个数组,表示这棵树的左子树的后序遍历序列</param>
/// <param name="rightPart">一个数组,表示这棵树的右子树的后序遍历序列</param>
void SplitArray(int[] sourceArray, int[] leftPart, int[] rightPart)
{
// 对于后序遍历,各部分对应的下标范围为:
// - [0, leftPart.Length):左子树的后序遍历
// - [leftPart.Length, leftPart.Length + rightPart.Length):右子树的后序遍历
// - [leftPart.Length + rightPart.Length, sourceArray.Length):根节点 // 复制左子树内容
Array.Copy(sourceArray, leftPart, leftPart.Length);
// 复制右子树内容
Array.Copy(sourceArray, leftPart.Length, rightPart, 0, rightPart.Length);
}
Solution
-
Construct Binary Tree from Inorder and Postorder Traversal
/// <summary>
/// 根据二叉树的中序遍历序列和后序遍历序列,构建这棵二叉树
/// </summary>
/// <param name="inorder">一个数组,表示二叉树的中序遍历序列</param>
/// <param name="postorder">一个数组,表示二叉树的后序遍历序列</param>
/// <returns>构建出的二叉树的根节点</returns>
public TreeNode BuildTree(int[] inorder, int[] postorder)
{
// 递归终止条件:序列的长度为 0,返回 null
if (inorder.Length == 0 || postorder.Length == 0)
return null;
// 从后序遍历序列中找到根节点的值
int rootVal = postorder.Last();
// 在中序遍历序列中找到根节点对应的下标,以便分出左右部分
int rootIndex = Array.IndexOf(inorder, rootVal); // 提前为后序遍历的两部分分配内存空间
int[] postorderLeft = new int[rootIndex - 0];
int[] postorderRight = new int[inorder.Length - (rootIndex + 1)]; // 建立根节点
TreeNode root = new TreeNode(rootVal); // 拆分中序遍历序列
SplitArray(inorder, rootIndex, out int[] inorderLeft, out int[] inorderRight); // 拆分后序遍历序列
SplitArray(postorder, postorderLeft, postorderRight); // 递归地调用该方法以构建左右子树
root.left = BuildTree(inorderLeft, postorderLeft);
root.right = BuildTree(inorderRight, postorderRight); return root;
} -
Construct Binary Tree from Preorder and Inorder Traversal
/// <summary>
/// 根据二叉树的中序遍历序列和前序遍历序列,构建这棵二叉树
/// </summary>
/// <param name="preorder">一个数组,表示二叉树的前序遍历序列</param>
/// <param name="inorder">一个数组,表示二叉树的中序遍历序列</param>
/// <returns>构建出的二叉树的根节点</returns>
public TreeNode BuildTree(int[] preorder, int[] inorder)
{
// 递归终止条件:序列的长度为 0,返回 null
if (inorder.Length == 0 || preorder.Length == 0)
return null;
// 从前序遍历序列中找到根节点的值
int rootVal = preorder[0];
// 在中序遍历序列中找到根节点对应的下标,以便分出左右部分
int rootIndex = Array.IndexOf(inorder, rootVal); // 提前为前序遍历的两部分分配内存空间
int[] preorderLeft = new int[rootIndex - 0];
int[] preorderRight = new int[inorder.Length - (rootIndex + 1)]; // 建立根节点
TreeNode root = new TreeNode(rootVal); // 拆分中序遍历序列
SplitArray(inorder, rootIndex, out int[] inorderLeft, out int[] inorderRight); // 拆分前序遍历序列
SplitArray(preorder, preorderLeft, preorderRight); // 递归地调用该方法以构建左右子树
root.left = BuildTree(preorderLeft, inorderLeft);
root.right = BuildTree(preorderRight, inorderRight); return root;
}