[LeetCode] 根据前序序列和中序序列重建二叉树

秒速五厘米 2022-08-04 09:16 110阅读 0赞

LeetCode 链接: [根据前序和中序序列重建二叉树][Link 1]

思路：

1、根据先序向量数组的值把中序向量数组一分为二，然后递归左右部分；  
2、设置全局 index 索引，作为先序遍历向量的下标,每次递归左子树之后减一。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        private int index = -1 ;
    	public TreeNode buildTree(int[] preorder, int[] inorder) {
            return btConstruct(preorder, inorder, 0, preorder.length - 1) ;
        }
    	
    	public TreeNode btConstruct(int[] preorder, int[] inorder, int l, int r) {
    		index ++ ;
    		if(l > r || r > preorder.length) {
    			return null ;
    		}
    		
    		TreeNode root = new TreeNode(preorder[index]) ;
    		int j ;
    		for(j = l; j <= r; j ++) {
    			if(preorder[index] == inorder[j]) {
    				break ;
    			}
    		}
    		
    		if(j <= r) {
    			root.left = btConstruct(preorder, inorder, l, j - 1) ;
    			index -- ;
    			root.right = btConstruct(preorder, inorder, j + 1, r) ;
    		}
    		
    		return root ;
    	}
    }

[Link 1]: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

发表评论取消回复

表情：

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

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

相关阅读

相关 C++实现利用前序序列和中序序列构建二叉树

前言：已知一个二叉树的中序序列和前序序列，或者中序序列和后序序列就可以唯一确定一个二叉树（必须知道中序序列），只知道前序和后序不能创建唯一的二叉树。 1.引例已知

红太狼/ 2023年07月20日 13:35/ 0 赞/ 43 阅读

相关 [LeetCode] 根据中序和后序序列重建二叉树

LeetCode 链接： [根据中序和后序序列重建二叉树][Link 1] 思路：主要在于左右子树根节点的寻找过程 1、右子树根节点为 postorder 向量容器中根节

待我称王封你为后i/ 2022年08月04日 09:18/ 0 赞/ 108 阅读

相关 [LeetCode] 根据前序序列和中序序列重建二叉树

LeetCode 链接: [根据前序和中序序列重建二叉树][Link 1] 思路： 1、根据先序向量数组的值把中序向量数组一分为二，然后递归左右部分； 2、设置全局 i

秒速五厘米/ 2022年08月04日 09:16/ 0 赞/ 111 阅读

相关根据前序遍历序列和中序遍历序列重建二叉树

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

柔光的暖阳◎/ 2022年07月16日 03:40/ 0 赞/ 160 阅读

相关根据前序遍历序列和中序遍历序列创建二叉树

一个前序遍历序列和一个中序遍历序列可以确定一颗唯一的二叉树。根据前序遍历的特点, 知前序序列(PreSequence)的首个元素(PreSequ

矫情吗；*/ 2022年07月15日 01:15/ 0 赞/ 160 阅读

相关根据前序遍历序列和中序遍历序列创建二叉树

一个前序遍历序列和一个中序遍历序列可以确定一颗唯一的二叉树。根据前序遍历的特点, 知前序序列(PreSequence)的首个元素(PreSequ

悠悠/ 2022年07月15日 01:15/ 0 赞/ 136 阅读

相关 C/C++面试题—重建二叉树【前序 + 中序-> 重建二叉树和后序 + 中序 -> 重建二叉树】

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

悠悠/ 2022年05月24日 06:09/ 0 赞/ 124 阅读

相关根据前序和中序遍历重建二叉树 java

根据前序和中序遍历重建二叉树 java 题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如

超、凢脫俗/ 2022年05月09日 09:30/ 0 赞/ 142 阅读

相关根据先序和中序序列重建二叉树（打印二叉树的后序序列）

1.重建条件我们知道，要重建二叉树，必须得有中序序列，有了中序，才可以划分出根结点的左子树和右子树。而由先序和后序可以很容易确定根结点，因此，先序和中序或者后序和中

叁歲伎倆/ 2022年04月15日 06:52/ 0 赞/ 132 阅读

相关如何根据前序遍历序列和中序遍历序列确定二叉树

假设某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，画出二叉树，并给出其后序遍历序列。分析过程：以下面的例题为例进行讲解：已知一棵二叉

心已赠人/ 2022年04月03日 06:36/ 0 赞/ 208 阅读