【刷算法】重建二叉树

Blackjun 发布于2019-08-22 18:50 / 3441人阅读

题目描述

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

分析

前序遍历是中左右的顺序，中序遍历是左中右的顺序，那么对于{1,2,4,7,3,5,6,8}和{4,7,2,1,5,3,8,6}来说，1是根节点，然后1把中序遍历的序列分割为两部分，“4，7，2”为1的左子树上的节点，“5，3，8，6”为1的右子树上的节点，这样递归的分解下去即可

代码实现

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
    var root = recon(0, pre.length-1, pre, 0, vin.length-1, vin);
    return root;
}

function recon(preStart, preEnd, pre, vinStart, vinEnd, vin){
    if(preStart > preEnd || vinStart > vinEnd) {
        return null;
    }

    var node = new TreeNode(pre[preStart]);

    for(var i = vinStart;i <= vinEnd;i++) {
        if(vin[i] === pre[preStart]){
            node.left = recon(preStart+1, preStart+i-vinStart, pre, vinStart, i-1, vin);
            node.right = recon(preStart+i-vinStart+1, preEnd, pre, i+1, vinEnd, vin);
        }
    }

    return node;
}

GPU云服务器云服务器二叉树算法最优二叉树算法图二叉树 python二叉树

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

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

【刷算法】对称的二叉树

摘要：题目描述请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。分析一般关于二叉树的题目，第一直觉是往递归上面靠，当然了，本题适不适合还暂时不知道。题目描述请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。分析一般关于二叉树的题目，第一直觉是往递归上面靠，当然了，本...

Forest10 2019-08-22 18:15 评论0 收藏0
【刷算法】二叉树中和为某一值的路径

摘要：题目描述输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。思路二叉树的大多数问题可以使用递归来解决，本题亦如此。题目描述输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。思路二叉树的大多数问题可以使用...

zxhaaa 2019-08-22 18:21 评论0 收藏0
【刷算法】翻转二叉树的递归和非递归解法

摘要：题目描述操作给定的二叉树，将其变翻转为源二叉树的镜像。输入描述解题思路递归版本首先，对数据结构比较了解的话会想到用递归来解决。所谓递归，在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法来自维基百科。题目描述操作给定的二叉树，将其变翻转为源二叉树的镜像。输入描述: 1 1 / ...

wangbjun 2019-08-22 18:06 评论0 收藏0
【刷算法】从上往下打印二叉树

摘要：题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。分析二叉树的层次遍历，可以借助队列的帮助实现题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。分析二叉树的层次遍历，可以借助队列的帮助实现 /* function TreeNode(x) { this.val = x; this.left = null; this.right =...

ShowerSun 2019-08-22 18:20 评论0 收藏0
【刷算法】LeetCode.236-二叉树的最近公共祖先

摘要：给定一个二叉树找到该树中两个指定节点的最近公共祖先。示例输入输出解释节点和节点的最近公共祖先是节点。说明所有节点的值都是唯一的。给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。示例 1: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。示例 ...

Joonas 2019-08-23 14:31 评论0 收藏0