JS实现二叉树的重建

深碍√TFBOYSˉ_ 2023-01-14 01:36 66阅读 0赞

### 文章目录 ###

*  1.根据前序+中序
 *  2.根据后序+中序

function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    }

1.  前序or后序用来确认根节点  
    前序中，根节点在第一个，后序中根节点在最后一个
2.  利用根节点将**中序**遍历数组分割为左子树、右子树 相关数据。  
    对于中序遍历，根节点左边的节点即左子树，根节点右边的节点即右子树。

# 1.根据前序+中序 #

function creatTree(pre, vin)
    {
        if(pre.length === 0 || vin.length === 0){
            return null;
        }
        //创建根节点，根节点是前序遍历的第一个数
        var root = pre[0];
        var tree = new TreeNode(root);
        //找到中序遍历根节点所在位置
        var index = vin.indexOf(root);
        tree.left = creatTree(pre.slice(1,index+1),vin.slice(0,index));
        tree.right = creatTree(pre.slice(index+1),vin.slice(index+1));
        return tree;
    }

# 2.根据后序+中序 #

function creatTree(pos, vin)
    {
        if(!pos || vin.length === 0){
            return null;
        }
        //创建根节点，根节点是后序遍历的最后一个数
        var root = pos[pos.length-1];
        var tree = new TreeNode(root);
        //找到中序遍历根节点所在位置
        var index = vin.indexOf(root);
        tree.left=creatTree(pos.slice(0,index),vin.slice(0,index))
        tree.right=creatTree(pos.slice(index,pos.length-1),vin.slice(index+1))
        return tree;
    }

[本文链接https://blog.csdn.net/qq\_39903567/article/details/115867151][https_blog.csdn.net_qq_39903567_article_details_115867151]

[https_blog.csdn.net_qq_39903567_article_details_115867151]: https://blog.csdn.net/qq_39903567/article/details/115867151

发表评论取消回复

表情：

评论列表（有 0 条评论，66人围观）

还没有评论，来说两句吧...

相关阅读

相关 JS实现二叉树的重建

文章目录 1.根据前序+中序 2.根据后序+中序 function TreeNode(x) { this.val = x;

深碍√TFBOYSˉ_/ 2023年01月14日 01:36/ 0 赞/ 67 阅读

相关重建二叉树

![这里写图片描述][70] class TreeNode { int val; TreeNode left; Tre

ゝ一世哀愁。/ 2022年05月26日 07:57/ 0 赞/ 186 阅读

相关重建二叉树（JS实现）

题目输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,

绝地灬酷狼/ 2022年05月15日 05:34/ 0 赞/ 122 阅读

相关重建二叉树

二叉树重建根据二叉树的前序遍历和中序遍历，重建二叉树。综合利用前序遍历和中序遍历的特点。 / 题目描述输入某二叉树的前序遍历和中序遍历的

Love The Way You Lie/ 2022年05月14日 15:48/ 0 赞/ 212 阅读

相关重建二叉树

重建二叉树输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。如前序\{1,2,4,7,3,5,6,8

亦凉/ 2022年04月24日 13:54/ 0 赞/ 189 阅读

相关重建二叉树

/ Definition for binary tree struct TreeNode { int val;

灰太狼/ 2022年04月03日 13:44/ 0 赞/ 247 阅读

相关重建二叉树

时间限制：1秒空间限制：32768K 热度指数：524408 算法知识视频讲解题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序

阳光穿透心脏的1/2处/ 2022年03月11日 20:44/ 0 赞/ 185 阅读

相关重建二叉树

题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6

古城微笑少年丶/ 2022年03月06日 12:26/ 0 赞/ 232 阅读

相关二叉树重建

给定二叉树的先序遍历序列和中序遍历序列，进行二叉树的重建以及后序遍历队列。突然看到这个问题。。发现之前的想法都忘记了=\_=||，果然算法题一日不写手生啊，还是得好好坚持

淡淡的烟草味﹌/ 2021年12月14日 04:15/ 0 赞/ 282 阅读

相关重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序

妖狐艹你老母/ 2021年09月23日 09:20/ 0 赞/ 365 阅读