剑指 Offer 33. 二叉搜索树的后序遍历序列 + 根据二叉树的后序遍历序列判断对应的二叉树是否存在
2024-08-29 20:17:37
剑指 Offer 33. 二叉搜索树的后序遍历序列
Offer_33
题目详情
题解分析
- 本题需要注意的是,这是基于一颗二叉排序树的题目,根据排序二叉树的定义,中序遍历序列就是数据从小到大的排序序列。
- 这里有很多的细节问题,特别是在递归时,需要注意递归的出口和判断条件。
解法一:传统的方法
package com.walegarrett.offer;
/**
* @Author WaleGarrett
* @Date 2021/2/1 16:45
*/
import java.util.Arrays;
/**
* 题目详情:输入一个整数数组,判断该数组是不是 **某二叉搜索树 ** 的后序遍历结果。
* 如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
*/
public class Offer_33 {
int[] postorder;
int[] inorder;
public boolean verifyPostorder(int[] postorder) {
this.postorder = postorder;
inorder = Arrays.copyOf(postorder, postorder.length);
Arrays.sort(inorder);//中序遍历序列
return rebuildBinaryTree(0, inorder.length - 1, 0, postorder.length -1);
}
boolean rebuildBinaryTree(int infrom, int inend, int postfrom, int postend){
if(inend < infrom || postend < postfrom)
return true;
int root = postorder[postend];
int index = -1;
for(int i = infrom; i<= inend; i++){
if(inorder[i] == root){
index = i;
break;
}
}
//System.out.println(infrom + " " + inend + " " + postfrom + " " + postend + " " +index);
if(index == - 1)
return false;
int numLeft = index - infrom;
return rebuildBinaryTree(infrom, index-1, postfrom, postfrom + numLeft -1) &&
rebuildBinaryTree(index+1, inend, postfrom + numLeft, postend - 1);
}
}
解法二:仅仅使用后序遍历序列进行递归分治
解法二来自:面试题33. 二叉搜索树的后序遍历序列(递归分治 / 单调栈,清晰图解)
class Solution {
public boolean verifyPostorder(int[] postorder) {
return recur(postorder, 0, postorder.length - 1);
}
boolean recur(int[] postorder, int i, int j) {
if(i >= j) return true;
int p = i;
while(postorder[p] < postorder[j]) p++;
int m = p;
while(postorder[p] > postorder[j]) p++;
return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
}
}
最新文章
- unity 利用ugui 制作技能冷却效果
- Beta阶段第五次Scrum Meeting
- 2014.7建兰NOIP模拟Day1 Running
- Kafka笔记--使用ubuntu为bocker(服务器)windows做producer和comsumer(客户端)
- How to use Request js (Node js Module) pools
- OpenCV面、人眼检测
- 第三十讲:Android之Animation(五)
- PHP学习路线图
- Supervisor: A Process Control System
- Python tutorial阅读之Python基本运算与基本变量
- unix中的rm,rmdir的使用
- 转载:curl 模拟请求
- D. Frets On Fire 前缀和+二分
- 数据结构(java版)学习笔记(一)——线性表
- BZOJ2843 极地旅行社 LCT
- Codeforces Round #404 (Div. 2) D. Anton and School - 2 数学
- VCL界面控件DevExpress VCL Controls发布v18.2.5|附下载
- [转]Poisson Distribution
- 抓包和测试Api类工具
- Fiddler 常用功能总结
热门文章
- 【bzoj 2597】[Wc2007]剪刀石头布(图论--网络流 最小费用最大流)
- B、小花梨的三角形(解题报告)
- java中static修改成员变量和函数和其他使用
- 郁闷的出纳员 HYSBZ - 1503
- Ubuntu中Unable to acquire the dpkg frontend lock (/var/lib/dpkg/lock-frontend)问题的解决
- Codeforces Round #658 (Div. 2) C1. Prefix Flip (Easy Version) (构造)
- ApiPost V5 升级指南
- XV6学习(14)Lab fs: File system
- k8s-0-集群
- OpenStack-知识点补充