算法之不定期更新（四）—— 从前序与中序遍历序列构造二叉树（2018-06-02）

charles_paul 发布于2019-08-26 11:57 / 1871人阅读

摘要：树的前序，中序遍历的结构如下图可以看出，通过前序遍历可以确定根节点，再通过中序遍历和根节点的位置可以确定出左子树和右子树。另外左子树的前序遍历和中序遍历的顺序跟在其父树中的顺序一样。因此可以确定有一种递归解法。

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

今天带来的是Leetcode上的一个经典题：从前序与中序遍历序列构造二叉树
原题干：

/**

Definition for a binary tree node.
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}

*/
/**

@param {number[]} preorder
@param {number[]} inorder
@return {TreeNode}

*/
input:

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

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


output： 树的根节点
条件：
树的结构为：{ val, left, right }

下面是我解决这个题的时候的思路

解题思路

这个题目考察的是对树结构和树遍历的熟悉程度。树的前序，中序遍历的结构如下图：

可以看出，通过前序遍历可以确定根节点，再通过中序遍历和根节点的位置可以确定出左子树和右子树。另外左子树的前序遍历和中序遍历的顺序跟在其父树中的顺序一样。

因此可以确定有一种递归解法。确定根和左右子树，递归用左右子树的前序和中序顺序去获取左右子树。

代码

var buildTree = function(preorder, inorder) {
    if (preorder.length === 0) {
        return null
    }
    let leftTreeLen = 0
    let rightTreeLen = 0
    let tag = 1
    for (let i = inorder.length - 1; i >= 0; i--) {
        if (inorder[i] !== preorder[0]) {
            if (tag) {
                rightTreeLen++
            } else {
                leftTreeLen++
            }
        } else if (inorder[i] === preorder[0]) {
            tag = false
        }
    }
    let root = new TreeNode(preorder[0]) // 根
    root.left = buildTree(preorder.slice(1, 1 + leftTreeLen), inorder.slice(0, leftTreeLen))
    root.right = buildTree(preorder.slice(1 + leftTreeLen), inorder.slice(-rightTreeLen))
    return root
};

晚上再更新一次，目测是有非递归的解法的。

本期算法小分享就到这里咯（leetcode正在做完探索里的中级。）如果有什么意见或者想法欢迎在评论区和我交流

云服务器超融合服务器二叉树遍历二叉树的遍历 JS二叉树遍历非递归二叉树遍历

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/107905.html

二叉树相关面试题【数据结构】

摘要：题目目录基础面试题二叉树的前序遍历二叉树的中序遍历二叉树的后续遍历结果相同的树另一棵树的子树二叉树的最大深度平衡二叉树判断对称二叉树进阶面试题二叉树的遍历及构建二叉树的分层遍历二叉树的最近公共祖先二叉搜索树与双向链表从前序 ...

Tamic 2021-10-11 10:58 评论0 收藏0
JavaScript算法之二叉搜索树

摘要：二叉搜索树的特性二叉搜索树由于其独特的数据结构，使得其无论在增删，还是查找，时间复杂度都是，为二叉树的高度。二叉搜索树的查找查找很简单，根据左子节点比该节点小，右子节点比该节点大的原则进行循环判断即可。什么是二叉树二叉树就是树的每个节点最多只能有两个子节点什么是二叉搜索树二叉搜索树在二叉树的基础上，多了一个条件，就是二叉树在插入值时，若插入值比当前节点小，就插入到左节点，否则插...

khlbat 2019-08-21 16:26 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0
数据结构：二叉树

摘要：链式存储结构由于二叉树的每个结点最多有两个孩子，所以为每个结点设计一个数据域和两个指针域。最终能得到二叉树的完整结构。这篇文章主要介绍树结构中的一种特殊存在——二叉树。主要内容有：二叉树的概念二叉树的基本结构二叉树的操作概念二叉树：每个结点最多有两个子结点，两个子结点是有次序的，且子结点次序不能颠倒。两个子结点一般称之为左结点及右结点。层次：在树中，节点的层次从...

Ashin 2019-05-23 17:30 评论0 收藏0
数据结构与算法:二叉树算法

摘要：因此，根据题目给出的先序遍历和中序遍历，可以画出二叉树选参考数据结构与算法描述实现二叉树算法浅谈数据结构二叉树慕课网实现二叉树算法前端树控件腾讯软件开发面试题内容衔接上一章数据结构与算法:常见排序算法内容提要什么是树　　- 为什么使用树二叉树二叉查找树红黑树Ｂ、Ｂ＋树堆伸展树树可以点击链接感受下笔者用d3.js画的tree https://codepen...

Little_XM 2019-08-22 11:09 评论0 收藏0