每日一题：LeetCode-105. 从前序与中序遍历序列构造二叉树

作者：半亩房顶

2023-12-07
北京
本文字数：1601 字
阅读完需：约 5 分钟

刷题使我快乐，满脸开心.jpg

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]输出: [3,9,20,null,null,15,7]

复制代码

示例 2:

输入: preorder = [-1], inorder = [-1]输出: [-1]

复制代码

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

思路

还是头一次思考构建树的问题，整理了下思路，发现其实考查的就是对于两种遍历方式的理解。

前序遍历：对于每一个节点及其左右子节点的组合来说，总是以根->左->右的顺序遍历节点中序遍历：对于每一个节点及其左右子节点的组合来说，总是以左->根->右的顺序遍历节点

基于这个特性，我们再来看两个遍历方式的数组，就可以用这个思路来分解问题

对于一棵树来说，前序遍历的第一个元素即是树的根节点
对于中序遍历数组中，根节点左边的元素都是其左子树的元素；根节点右边的元素都是其右子树的元素

有了这个概念，我们就可以分解问题了：

一层层往下拆解子树，这就是递归方法的递归条件
直到没有节点、仅剩一个节点，此时就可以直接返回了，这就是递归方法的退出条件

至此，递归方法的要素就凑齐了，这里我的代码，不如官方解法简洁，但是感觉能更加直接的看出拆解左右子树的过程

另外放了官方递归的代码，方便看下更简洁的写法~

老样子，细节在代码注释了，上代码~

代码

个人递归解法

func buildTree(preorder []int, inorder []int) *TreeNode {    // 四个参数均为数组下标    var getTree func(inStart, inEnd, preStart, preEnd int) *TreeNode    getTree = func(inStart, inEnd, preStart, preEnd int) *TreeNode {        if preStart > preEnd {            return nil        }
        root := &TreeNode{Val: preorder[preStart]}        // 可有可无，不写就会多进一层递归，然后return nil返回        if preStart == preEnd {            return root        }
        i := inStart        for ; i <= inEnd; i++ {            if preorder[preStart] == inorder[i] {                break            }        }        // 四个参数均为数组下标        // 前序遍历中，左子树的节点们就是以根节点之后第一个元素开始        leftPreStart := preStart + 1        // 根据中序遍历数组，可以知道根节点位置和起始位置之间的差值就是左子树长度        leftLen := i - inStart        // 前序遍历中，右子树的节点起点就是以左子树起点坐标加上左子树长度        rightPreStart := leftPreStart + leftLen        root.Left = getTree(inStart, i-1, leftPreStart, rightPreStart-1)        root.Right = getTree(i+1, inEnd, rightPreStart, preEnd)        return root    }    return getTree(0, len(inorder)-1, 0, len(preorder)-1)}

复制代码

官方递归解法

func buildTree(preorder []int, inorder []int) *TreeNode {    if len(preorder) == 0 {        return nil    }    root := &TreeNode{preorder[0], nil, nil}    i := 0    for ; i < len(inorder); i++ {        if inorder[i] == preorder[0] {            break        }    }    root.Left = buildTree(preorder[1:len(inorder[:i])+1], inorder[:i])    root.Right = buildTree(preorder[len(inorder[:i])+1:], inorder[i+1:])    return root}

复制代码

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/d1817e0b8e82ab8e1b3aba56e】。文章转载请联系作者。

半亩房顶

关注

人生那么长，能写多少bug？ 2018-11-16 加入

我希望，自己永远是自己。我希望，远离bug。

发布

暂无评论

创作场景

每日一题：LeetCode-105. 从前序与中序遍历序列构造二叉树

题目

思路

代码

个人递归解法

官方递归解法

半亩房顶

评论