精华内容
下载资源
问答
  • 105、从前序与中序遍历构造二叉树 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] ...

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

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

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

    例如,给出

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

    返回如下的二叉树:

        3
       / \
      9  20
        /  \
       15   7

    //思路:preorder第一个元素为root,在inorder中找到root,root左面为左子树,右面为右子树,不断递归。如下图所示。

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
     public TreeNode buildTree(int[] preorder,int[] inorder) {
    		//思路:在preorder第一个结点是根节点,在inorder中找到root,root左面是左子树,右面是右子树
    		if(preorder.length==0)
    			return null;
    		return buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    	}
    	public TreeNode buildTree(int[] preorder,int l1,int r1,int[] inorder,int l2,int r2) {
    		if(l1>r1)
    			return null;
    		if(l1==r1)
    			return new TreeNode(preorder[l1]);
    		TreeNode root=new TreeNode(preorder[l1]);
    		int i=l2;
    		while(preorder[l1]!=inorder[i])
    			i++;
    		root.left=buildTree(preorder,l1+1,l1+i-l2,inorder,l2,i-1);
    		root.right=buildTree(preorder,l1+i-l2+1,r1,inorder,i+1,r2);
    		return root;
    	}
    }

    106、从中序与后续遍历构造二叉树

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

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

    例如,给出

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

    返回如下的二叉树:

        3
       / \
      9  20
        /  \
       15   7
    

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            //思路:postorder最后一个元素为root,在inorder中找到root,root左面为左子树,右面为右子树,不断递归
    		if(postorder.length==0)
    			return null;
    		return buildTree(postorder,0,postorder.length-1,inorder,0,inorder.length-1);
    	}
    	public TreeNode buildTree(int[] postorder,int l1,int r1,int[] inorder,int l2,int r2) {
    		if(l1>r1)
    			return null;
    		if(r1==l1)
    			return new TreeNode(postorder[l1]);
    		TreeNode root=new TreeNode(postorder[r1]);
    		int i=l2;
    		while(inorder[i]!=postorder[r1])
    			i++;
    		root.left=buildTree(postorder,l1,l1+i-l2-1,inorder,l2,i-1);
    		root.right=buildTree(postorder,l1+i-l2,r1-1,inorder,i+1,r2);
    		return root;
        }
    }
    展开全文
  • 从中序与后序遍历序列构造二叉树 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下...

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

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

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

    例如,给出

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

    返回如下的二叉树:

      3   
     / \   
    9  20
      /  \   
     15   7
    

    解题思路

    递归,从上到下求解,根据中序遍历和后序遍历的特点,可求得:
    1.头节点位于后序遍历的最后一个元素;
    2.头节点可将中序遍历分为左右两部分;
    3.中序遍历的左右两部分存在递归;

    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {number[]} inorder
     * @param {number[]} postorder
     * @return {TreeNode}
     */
    //递归,根据中序遍历和后序遍历的特点进行构造树
    var buildTree = function(inorder, postorder) {
       if(!inorder.length || !postorder.length){
           return null
       }
       let node = postorder.pop()//头节点
       let index = inorder.indexOf(node) //头节点在中序遍历数组中的位置
       let root = new TreeNode(node) //构造一棵树
        root.left = buildTree(inorder.slice(0,index),postorder.slice(0,index))
        root.right = buildTree(inorder.slice(index+1),postorder.slice(index))
    
        return root
    
    };
    
    展开全文
  • 从前序与中序遍历序列构造二叉树 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的...

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

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

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

    例如,给出

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

      3   
     / \ 
    9  20
      /  \   
     15   7
    

    解题思路

    递归,自顶向下求解
    根据前序遍历和中序遍历的特点,前序遍历中,序列的第一个元素就是头节点的位置,获取头节点,在中序遍历中可根据头节点的值,返回头节点在中序遍历中的位置,此位置将中序遍历分为左右两个部分,左边的部分为左子树的值,右边的部分为右子树的值,递归调用此函数,可分别求得左右子树的节点。

    /**
     * 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}
     */
    //迭代,根据前序遍历和中序遍历的特点,进行树的构造
    var buildTree = function(preorder, inorder) {
        if(!preorder.length || !inorder.length){
            return null
        }
        var node = preorder.shift() //获取头节点
        var index = inorder.indexOf(node)//获取头节点在中序遍历中的位置
        var root = new TreeNode(node) //新建一棵树
        root.left = buildTree(preorder.slice(0,index),inorder.slice(0,index))
        root.right = buildTree(preorder.slice(index),inorder.slice(index+1))
        return root
    };
    

    在这里插入图片描述

    展开全文
  • var constructMaximumBinaryTree = function(nums) { let getMaxNum = function (nums) { if (nums.length < 1) return -1; let max = -1; let maxIndex =... nums.forEach((item, index) =...
  • 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树: 3 / 9 20 / 15 7 2 ...

    1 题目

    根据一棵树的中序遍历与后序遍历构造二叉树。
    注意:
    你可以假设树中没有重复的元素。
    例如,给出
    中序遍历 inorder = [9,3,15,20,7]
    后序遍历 postorder = [9,15,7,20,3]
    返回如下的二叉树:
    3
    /
    9 20
    /
    15 7

    2 思路

    这道题的主要思路跟从中序和前序序列构造二叉树,只不过前序换成了后序,我们就需要先构造右子树,再构造左子树

    3代码

    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {number[]} inorder
     * @param {number[]} postorder
     * @return {TreeNode}
     */
    var buildTree = function(inorder, postorder) {
    function d(pArr, inArr, begin, end) {
        if (begin > end) return null;
    
        let nodeValuie = pArr.pop();
        let index = inArr.indexOf(nodeValuie);
        let node = new TreeNode(nodeValuie);
    
        node.right = d(pArr, inArr, index + 1, end);
        node.left = d(pArr, inArr, begin, index - 1);
    
        return node;
      }
    
      return d(postorder, inorder, 0, inorder.length - 1);
    
    
      function TreeNode(val) {
        this.val = val;
        this.left = this.right = null;
      }
    };
    
    展开全文
  • 【LeetCode 105】从前序与中序遍历序列构造二叉树 【LeetCode 889】根据前序和后序遍历构造二叉树 题目描述 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序...
  • LeetCode106 从中序与后序遍历序列构造二叉树题目解题解题一:递归解题二:迭代 题目 解题 与 LeetCode105 从前序与中序遍历序列构造二叉树 的解题思路一致。 主要是要找出如下关系: 中序遍历:[ [左子树], 根节点...
  • 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序遍历 inorder =[9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树: 3 / \ 9 20 / \ ...
  • 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder =[3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3 / \ 9 20 / \ ...
  • 【LeetCode 105】从前序与中序遍历序列构造二叉树 【LeetCode 106】从中序与后序遍历序列构造二叉树 题目描述 返回与给定的前序和后序遍历匹配的任何二叉树。 pre 和 post 遍历中的值是不同的正整数。 示例: 输入...
  • 1、首先是利用构造函数创建一个二叉树的的数据结构 (注意:在js中没有{1,2,3}这样的变量,故使用数组)function TreeNode(x) { this.val = x; this.left = null; this.right = null; }2、先分析,二叉树先序...
  • LeetCode105 从前序与中序遍历序列构造二叉树题目解题解题一:递归解题二:迭代 题目 没有重复元素这一点很重要,否则无法去定位。 解题 解题一:递归 // javascript var buildTree = function(preorder, inorder...
  • 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3 / 9 20 / 15 7 2 ...
  • 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 递归 /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right ...
  • 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 递归 /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right ...
  • 根据一棵树的前序遍历与中序遍历构造二叉树。 思路: 1.根据前序数组,找到根节点 2.根据中序数组中的根节点,找到左子树的长度 3.根据左子树的长度,找到左右子树的前序数组和中序数组 4.递归调用,直到前序数组为...
  • 中:从前序与中序遍历序列构造二叉树 英:Construct Binary Tree from Preorder and Inorder Traversal 切题口 (1)inorder: 从左到右递归存放着,当前root, 左子树的root,右子树的root (2)preorder: 当前...
  • 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3 / \ 9 20 / \ 15...
  • // 二叉树的根节点 let head = new TreeNode(preorder[0], null, null); // 根节点在中序遍历中的位置 let idx = inorder.indexOf(preorder[0]); head.left = buildTree(preorder.slice(1, idx+...
  • 从前序与中序遍历序列构造二叉树 题目描述 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] ...
  • 题目 思路 后序遍历的分布为 [左子树结点,右子树结点,根结点] 后序遍历的最后一个元素为根节点 获取根节点在中序遍历中的索引 索引值变向的告诉了我们左右子树节点数 根据节点数可将后续遍历中的左右子树区分开 ...
  • 105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode) 发布:2021年9月9日15:13:50 问题描述及示例 给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。 示例 1: Input: ...
  • 返回与给定的前序和后序遍历匹配的任何二叉树。 pre 和 post 遍历中的值是不同的正整数。 递归: var constructFromPrePost = function(pre, post) { if (!pre.length) return null const root = new TreeNode(pre...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,071
精华内容 2,028
热门标签
关键字:

js构造二叉树