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

Dear 丶 2021-09-27 09:02 189阅读 0赞

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

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

例如，给出

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

3  
/ \\  
9 20  
/ \\  
15 7

解题思路：采用递归  
根据：1.preorder 数组的开始节点为根节点  
2。根据该根节点可以找到左子树和右子树。

public TreeNode buildTree(int[] preorder, int[] inorder) {
            return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
        }
    
        private TreeNode build(int[] preorder, int pre_start, int pre_end, int[] inorder, int in_start, int in_end) {
            if(pre_start > pre_end || in_start > in_end )
                return null ;
            TreeNode root = new TreeNode(preorder[pre_start]);
            int index = 0;
            for(int i = in_start ;i<=in_end;i++){
                if(inorder[i] == preorder[pre_start]){
                    index = i ;
                    break;
                }
            }
            root.left = build (preorder,pre_start + 1,pre_start + (index - in_start),inorder,in_start,index-1);
            root.right = build (preorder,pre_start + (index - in_start) + 1,pre_end,inorder,index+1,in_end);
            return root;
        }

发表评论取消回复

表情：

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

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

相关阅读

相关 105. 从前序与中序遍历序列构造二叉树

先要知道一个结论，前序/后序+中序序列可以唯一确定一棵二叉树，所以自然而然可以用来建树。看一下前序和中序有什么特点，前序1,2,4,7,3,5,6,8 ，中序4,7,...

不念不忘少年蓝@/ 2024年04月18日 22:31/ 0 赞/ 78 阅读

相关【LeetCode】105. 从前序与中序遍历序列构造二叉树

> 作者：小卢 > > 专栏：《Leetcode》 > > 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》 > > ![7d63d497b511410

雨点打透心脏的1/2处/ 2024年03月16日 13:49/ 0 赞/ 26 阅读

相关 105. 从前序与中序遍历序列构造二叉树

[105. 从前序与中序遍历序列构造二叉树][105.] 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorde

矫情吗；*/ 2023年10月04日 18:27/ 0 赞/ 17 阅读

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

一、前言标签：树\_构建二叉树。问题来源LeetCode 105难度：中等。问题链接：[https://leetcode-cn.com/problems/con

痛定思痛。/ 2023年03月01日 12:34/ 0 赞/ 27 阅读

相关【LeetCode 105】从前序与中序遍历序列构造二叉树

相似题目： [【LeetCode 106】从中序与后序遍历序列构造二叉树][LeetCode 106] [【LeetCode 889】根据前序和后序遍历构造二叉树

叁歲伎倆/ 2022年11月30日 01:58/ 0 赞/ 108 阅读

相关 leetcode 105 从前序与中序遍历序列构造二叉树

前言题目：[105. 从前序与中序遍历序列构造二叉树][105.] 参考题解：[leetcode 106 从中序与后序遍历序列构造二叉树][leetcode 106]

悠悠/ 2022年08月28日 13:43/ 0 赞/ 127 阅读

相关【LeetCode】105. 从前序与中序遍历序列构造二叉树

题目链接：[https://leetcode-cn.com/problems/symmetric-tree/description/][https_leetcode-cn.co

我不是女神ヾ/ 2022年05月13日 17:27/ 0 赞/ 134 阅读

相关 leetcode 105 从前序与中序遍历序列构造二叉树

题意根据一棵树的前序遍历与中序遍历构造二叉树。注意: 你可以假设树中没有重复的元素。例如，给出前序遍历 preorder = \[3,9,20,15,7

迈不过友情╰/ 2022年04月11日 12:09/ 0 赞/ 135 阅读

相关 105-从前序与中序遍历序列构造二叉树

题目描述根据一棵树的前序遍历与中序遍历构造二叉树。注意: 你可以假设树中没有重复的元素。例如，给出前序遍历 preorder

刺骨的言语ヽ痛彻心扉/ 2022年01月15日 15:19/ 0 赞/ 156 阅读

相关 LeetCode105. 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。注意: 你可以假设树中没有重复的元素。例如，给出前序遍历 preorder = \[3,9,20,15,7\] 中

Dear 丶/ 2021年09月27日 09:02/ 0 赞/ 190 阅读