LeetCode105. 从前序与中序遍历序列构造二叉树

栏目: 数据库 · 发布时间: 5年前

内容简介:根据一棵树的前序遍历与中序遍历构造二叉树你可以假设树中没有重复的元素。例如,给出

描述

根据一棵树的前序遍历与中序遍历构造二叉树

注意:

你可以假设树中没有重复的元素。

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:

3
   / \
  9  20
    /  \
   15   7

思路

  • 前序遍历中,第一个节点即根节点
  • 在中序遍历中,找出第一个节点的位置,根节点前面的 L 个数据,即根节点左子树的中序遍历数据,前序遍历中根节点后面的 L 个数据即左子树的前序遍历
  • 右子树同上
  • 简而言之,确定了根节点,确定了左子树和右子树的数据,递归对左子树和右子树进行重建

代码实现

// 根据一棵树的前序遍历与中序遍历构造二叉树

// TreeNode Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }

    //前序遍历的第一个节点即根节点
    res := &TreeNode{
        Val: preorder[0],
    }

    if len(preorder) == 1 {
        return res
    }

    // 在中序遍历中,根节点前面的即根节点的左子树,后面的即右子树

    //匿名函数
    idx := func(val int, nums []int) int {
        for i, v := range nums {
            if v == val {
                return i
            }
        }
        return -1
    }(res.Val, inorder)
    if idx == -1 {
        panic("data error")
    }

    //递归,构建根节点左子树和右子树
    res.Left = buildTree(preorder[1:idx+1], inorder[:idx])
    res.Right = buildTree(preorder[idx+1:], inorder[idx+1:])
    return res
}

题目来源

105. 从前序与中序遍历序列构造二叉树

GitHub

本文为原创文章,转载注明出处,欢迎扫码关注公众号 楼兰 或者网站 https://lovecoding.club ,第一时间看后续精彩文章,觉得好的话,顺手分享到朋友圈吧,感谢支持。

LeetCode105. 从前序与中序遍历序列构造二叉树


以上所述就是小编给大家介绍的《LeetCode105. 从前序与中序遍历序列构造二叉树》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

数据结构与算法

数据结构与算法

许卓群、杨冬青、唐世渭、张铭 / 高等教育出版社 / 2004-1 / 29.50元

《数据结构与算法》把数据结构的原理和算法分析技术有机地结合在一起,系统地介绍了各种类型的数据结构和排序、检索的各种算法,还引入了一些比较高级的数据结构及相关的算法分析技术。.《数据结构与算法》分为基本数据结构、排序和检索、高级数据结构三部分。借助抽象数据类型,从逻辑结构的角度系统地介绍了线性表、字符串、二叉树、树和图等各种基本数据结构;从算法的角度讨论排序、检索和索引算法;从应用的角度介绍了一些复......一起来看看 《数据结构与算法》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

SHA 加密
SHA 加密

SHA 加密工具

html转js在线工具
html转js在线工具

html转js在线工具