【题解二连发】Construct Binary Tree from Inorder and Postorder Traversal & Construct Binary Tree from Preorder and Inorder Traversal

时间:2023-03-09 09:53:17
【题解二连发】Construct Binary Tree from Inorder and Postorder Traversal & Construct Binary Tree from Preorder and Inorder Traversal

LeetCode 原题链接

题目大意

  1. 给定一棵二叉树的中序遍历和后序遍历,求这棵二叉树的结构。
  2. 给定一棵二叉树的前序遍历和中序遍历,求这棵二叉树的结构。

样例

  1. Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]
    Output: [3, 9, 20, null, null, 15, 7]
  2. 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;
    }