- 浏览: 174871 次
- 性别:
- 来自: 济南
文章分类
最新评论
本文列举leetcode中两个关于构造二叉树的题目。
1,Construct Binary Tree from Inorder and Postorder Traversal
已知中序遍历序列,和后序遍历序列,通过这两个序列构造二叉树。
通过后序遍历序列的最后元素,我们总能找到根节点,然后通过这个值可以将中序序列分为两部分,然后在递归左右两部分。代码如下:
2,Construct Binary Tree from Preorder and Inorder Traversal
已知中序遍历序列和前序遍历序列,构造二叉树
和上一题类似,我们从前序遍历序列中的第一位元素,来将中序序列分为两部分,即分别为根节点的左子树和右子树,递归左子树和右子树,代码如下:
1,Construct Binary Tree from Inorder and Postorder Traversal
已知中序遍历序列,和后序遍历序列,通过这两个序列构造二叉树。
通过后序遍历序列的最后元素,我们总能找到根节点,然后通过这个值可以将中序序列分为两部分,然后在递归左右两部分。代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { if(inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0) return null; TreeNode root = new TreeNode(postorder[postorder.length-1]); int i = 0; for(i = 0; i < inorder.length; i++) { if(inorder[i] == postorder[postorder.length-1]) break; } int[] lp = Arrays.copyOfRange(postorder, 0, i); int[] li = Arrays.copyOfRange(inorder, 0, i); int[] rp = Arrays.copyOfRange(postorder, i, postorder.length - 1); int[] ri = Arrays.copyOfRange(inorder, i + 1, inorder.length); root.left = buildTree(li, lp); root.right = buildTree(ri, rp); return root; } }
2,Construct Binary Tree from Preorder and Inorder Traversal
已知中序遍历序列和前序遍历序列,构造二叉树
和上一题类似,我们从前序遍历序列中的第一位元素,来将中序序列分为两部分,即分别为根节点的左子树和右子树,递归左子树和右子树,代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder == null || inorder == null || preorder.length == 0) return null; TreeNode root = new TreeNode(preorder[0]); int i = 0; for(i = 0; i < inorder.length; i++) { if(inorder[i] == preorder[0]) break; } root.left = buildTree(Arrays.copyOfRange(preorder,1, i+1), Arrays.copyOfRange(inorder,0,i)); root.right = buildTree(Arrays.copyOfRange(preorder, i+1, preorder.length), Arrays.copyOfRange(inorder, i+1, inorder.length)); return root; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 229Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 233You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 349Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 343Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 463Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 526Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 438Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 625Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 436The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 394Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 522Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 543Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 379All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 873Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 886Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 564Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 612Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 772Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 741You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 635For a undirected graph with tre ...
相关推荐
leetcode的题目:Balanced Binary Tree
题目二叉树所有路径题解* Definition for a binary tree node.* function TreeNode(val) {* @para
leetcode伪代码merge-two-binary-tree 题目解读: 题目来源: 原文: Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the...
Construct Binary Tree from Inorder and Postorder Traversal 二叉查找树 Unique Binary Search Trees Unique Binary Search Trees II Validate Binary Search Tree Convert Sorted Array to Binary Search Tree ...
leetcode 数据结构题目中的答案,已经调试,直接运行,求二叉树的最小深度
二叉树的直径(diameter-of-binary-tree) 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 ...
leetcode做过的LeetCode的题目记录一下。对一些比较经典的题型进行分类总结。... Binary Tree Right Side View【2020-01-15】130. Surrounded Regions【2020-01-09】114. Flatten Binary Tree to Linked List
2013湘潭大学邀请赛题目 Alice and Bob Binary Search Tree Coins DNA Edges of Triangle Five Tiger Goddess Hurry Up I Love Military Chess Jack’s sequence
题目地址:思路后序遍历左 - 右 - 根代码* Definition for a binary tree node.* function TreeNode(va
示例:返回它的最小深度 2.Related Topics树深度优先搜索广度优先搜索题目代码* Definition for a binary tree nod
题目地址:思路这个题简单,使用二叉树,先循环左边的,再循环右边的,递归思想代码* Definition for a binary tree node.* fun
Binary Tree 题号 难度 题目名称及解答 C++ Java Python 中等 中等 中等 104 简单 105 中等 111 简单 144 中等 226 简单 230 中等 236 中等 297 困难 429 简单 589 简单 590 简单 实战题目 - 分治 题号 难度 题目...
##正好看见LeetCode可以刷Swift的题目 开始慢慢刷 swift有playground 做起来还是相当方便的 已完成题目 ----2016.9.30 两数循环 1. Two Sum 两数相加 2. Add Two Numbers 链表翻转 61. Rotate List 最大不同 318. ...
切题四件套 Clarification 明确题目意思 Possible solutions compare(time/space) optimal(加强) Coding(多写) Test cases Deliberate Practicing 坚持、刻意练习 练习缺陷、弱点地方 不舒服、不爽、枯燥 算法与数据...
construct-binary-tree-from-preorder-and-inorder-traversal 无官方题解 106 construct-binary-tree-from-inorder-and-postorder-traversal 无官方题解 116 populating-next-right-pointers-in-eac
题目链接: https://leetcode-cn.com/problems/binary-tree-right-side-view/ 解题思路: 树的层序遍历,先放左节点,再放右节点 每次将一层都放完的时候,将最后一个放入的元素加入到结果集中,其余直接清空 然后...
leetcode添加元素使和等于 Leetcode-tree 94题 Binary Tree Inorder Traversal 对于树的问题,大多数我们都会使用递归的方法。原因是树的左子树也是树,右子树也是树,使用递归的...动态规划题目特点: 计数型: -有
leetcode 530 力扣在线评委 # 问题 困难 解决方案 1 简单的 2 中等的 3 中等的 ...Binary Tree Preorder Traversal 2016.06.06 94. Binary Tree Inorder Traversal 318. Maximum Product of Word Length
总结 (基于Python3) 面试题目主要考察 数据结构 (Data Structure),算法 (Algorithm),以及套路 (Pattern) 资源 刷题 一开始先忽略 hard 题,实习面试一般考 medium/easy 题,全职面试可能考 hard 题 每个 topic ...
binarytree 二叉树 design 设计类 divideconquer 分治 dynamicprogramming 动态规划 背包问题 序列问题 极大化极小问题 路径问题 记忆化搜索 最长上升序列 greedy 区间问题 heap 堆 linklist 链表 math 数学 ...