从中序与后序遍历序列构造二叉树

[编程题]从中序与后序遍历序列构造二叉树

热度指数：5529 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树的中序与后序遍历结果，请你根据两个序列构造符合这两个序列的二叉树。

数据范围：二叉树的节点数满足 $1 \le n \le 1000 \$ ，节点上的值满足 $|val| \le 10^9 \$ ，保证节点的值各不相同

例如输入[2,1,4,3,5],[2,4,5,3,1]时，

根据中序遍历的结果[2,1,4,3,5]和后序遍历的结果[2,4,5,3,1]可构造出二叉树{1,2,3,#,#,4,5}，如下图所示：

示例1

输入

[1],[1]

输出

{1}

示例2

输入

[2,1,4,3,5],[2,4,5,3,1]

输出

{1,2,3,#,#,4,5}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

查看答案及解析

在加班的勇士很爱吃

package main
//import "fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param inorder int整型一维数组 中序遍历序列
 * @param postorder int整型一维数组 后序遍历序列
 * @return TreeNode类
*/
func buildTree( inorder []int ,  postorder []int ) *TreeNode {
    // write code here
    if len(postorder) == 0{
        return nil
    }
    newNode := new(TreeNode)
    newNode.Val = postorder[len(postorder) - 1]
    for i := 0; i < len(inorder); i++{
        if newNode.Val == inorder[i]{
            newNode.Left = buildTree(inorder[:i], postorder[:i])
            newNode.Right = buildTree(inorder[i+1:], postorder[i:len(postorder)-1])
            return newNode
        }
    }
    return newNode
}

发表于 2024-04-11 22:09:09 回复(0)