Go 刷 leetcode|从前序与中序遍历序列构造二叉树

Go语言精选

共 892字,需浏览 2分钟

 ·

2020-08-05 00:45

今天为大家讲解 LeetCode 第 105 题,是一道关于数组和树的题目。

题目描述

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

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

例如,给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树:

    3
/ \
9 20
/ \
15 7
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

preorder第一个元素为root,在inorder里面找到root,在它之前的为左子树(长stopIndex),之后为右子树。preorder[1]到preorder[stopIndex]为左子树,之后为右子树,分别递归。

代码实现

//go
/**
 * 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
    }
    root := &TreeNode{preorder[0], nilnil}
    i := 0
    // 在inorder里root的下标
    for ; i < len(inorder); i++ {
        if inorder[i] == preorder[0] {
            break
        }
    }
    // root前的长度,即左子树的长度
    stopIndex := len(inorder[:i])+1
    root.Left = buildTree(preorder[1:stopIndex], inorder[:i])
    root.Right = buildTree(preorder[stopIndex:], inorder[i+1:])
    return root
}

郑重声明:

所展示代码已通过 LeetCode 运行通过,请放心食用~



推荐阅读



学习交流 Go 语言,扫码回复「进群」即可


站长 polarisxu

自己的原创文章

不限于 Go 技术

职场和创业经验


Go语言中文网

每天为你

分享 Go 知识

Go爱好者值得关注


浏览 30
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报