当前位置:网站首页>leetcode刷题:二叉树17(从中序与后序遍历序列构造二叉树)
leetcode刷题:二叉树17(从中序与后序遍历序列构造二叉树)
2022-07-05 19:52:00 【涛涛英语学不进去】
106.从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树:
难度还好,递归法。终止条件是 两个数组的长度都为 0 时,返回 null 。后序遍历 左 右 根 。每次构造后序遍历时,后序数组的最后一个总是根结点,再根据这个根结点,还有题目规定 无重复元素,则在中序数组中找到当前根结点,以它为界限把中序数组分成左子树的中序数组和右子树的中序数组。而中序数组中 根结点 的位置,刚好放到后序数组中,该位置往前 是 左子树的后序遍历,该位置包括该位置往后 直到 倒数第二个元素 是右子树的后序遍历,最后一个为根结点。
再以此左子树的先、后数组 和 右子树的先、后数组做递归即可。
package com.programmercarl.tree;
/** * @ClassName BuildTree * @Descriotion TODO * @Author nitaotao * @Date 2022/7/5 12:37 * @Version 1.0 * https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ * 106. 从中序与后序遍历序列构造二叉树 **/
public class BuildTree {
/** * @param inorder 中序遍历 1 2 * @param postorder 后序遍历 2 1 * @return */
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder.length == 0 && postorder.length == 0) {
return null;
}
//上个数组的长度是相等的,因为元素个数相同
//后序遍历的第一个元素为根结点
TreeNode root = new TreeNode(postorder[postorder.length - 1]);
//在中序遍历中找到根结点
int rootIndex = 0;
for (int i = 0; i < inorder.length; i++) {
if (root.val == inorder[i]) {
rootIndex = i;
}
}
//中序数组分成左子树和右子树
int[] leftIn = new int[rootIndex];
int[] rightIn = new int[inorder.length - rootIndex - 1];
for (int i = 0; i < inorder.length; i++) {
if (i < rootIndex) {
leftIn[i] = inorder[i];
} else if (i > rootIndex) {
rightIn[i-rootIndex-1] = inorder[i];
}
}
//后序遍历数组 前rootIndex位是左子树的,后rootIndex位是右子树
int[] leftPost = new int[rootIndex];
int[] rightPost = new int[inorder.length - rootIndex - 1];
//最后一位结点,已经作为根结点被构建了。
for (int i = 0; i < postorder.length - 1; i++) {
if (i < rootIndex) {
leftPost[i] = postorder[i];
} else {
rightPost[i - rootIndex] = postorder[i];
}
}
//构建左右子树
root.left = buildTree(leftIn, leftPost);
root.right = buildTree(rightIn, rightPost);
return root;
}
public static void main(String[] args) {
new BuildTree().buildTree(new int[]{
1, 2}, new int[]{
2, 1});
}
}
边栏推荐
- C - sequential structure
- That's awesome. It's enough to read this article
- Android interview, Android audio and video development
- Bitcoinwin (BCW) was invited to attend Hanoi traders fair 2022
- How to apply smart contracts more wisely in 2022?
- What do software test engineers do? How about the prospect of treatment?
- openh264解码数据流向分析
- Information / data
- 95后阿里P7晒出工资单:狠补了这个,真香...
- 函数的概念及语法
猜你喜欢
third-party dynamic library (libcudnn.so) that Paddle depends on is not configured correctl
Xaas trap: all things serve (possible) is not what it really needs
Interviewer: what is the internal implementation of set data types in redis?
不愧是大佬,字节大牛耗时八个月又一力作
Inventory of the most complete low code / no code platforms in the whole network: Jiandao cloud, partner cloud, Mingdao cloud, Qingliu, xurong cloud, Jijian cloud, treelab, nailing · Yida, Tencent clo
Summer Challenge database Xueba notes, quick review of exams / interviews~
Bitcoinwin (BCW)受邀参加Hanoi Traders Fair 2022
Apprentissage du projet MMO I: préchauffage
Microwave radar induction module technology, real-time intelligent detection of human existence, static micro motion and static perception
Worthy of being a boss, byte Daniel spent eight months on another masterpiece
随机推荐
不愧是大佬,字节大牛耗时八个月又一力作
[OBS] qstring's UTF-8 Chinese conversion to blog printing UTF-8 char*
司空见惯 - 英雄扫雷鼠
Information / data
Force buckle 1200 Minimum absolute difference
Multi branch structure
Webuploader file upload drag upload progress monitoring type control upload result monitoring control
Which securities company is better and which platform is safer for mobile account opening
Recommended collection, my Tencent Android interview experience sharing
Force buckle 729 My schedule I
Complete interview questions for interviewers and senior Android engineers in front-line Internet enterprises
What do software test engineers do? How about the prospect of treatment?
CADD课程学习(7)-- 模拟靶点和小分子相互作用 (半柔性对接 AutoDock)
The problem of returning the longtext field in MySQL and its solution
Debezium series: PostgreSQL loads the correct last submission LSN from the offset
【C语言】字符串函数及模拟实现strlen&&strcpy&&strcat&&strcmp
Is it safe for Guosen Securities to open an account online?
安卓面试宝典,2022Android面试笔试总结
Interviewer: what is the internal implementation of set data types in redis?
Successful entry into Baidu, 35K monthly salary, 2022 Android development interview answer