判断是否为二叉搜索树的后序遍历序列
发布日期:2021-06-30 19:56:21
浏览次数:2
分类:技术文章
本文共 1201 字,大约阅读时间需要 4 分钟。
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。
题目链接:
知识点:
二叉排序树(Binary Sort Tree),又称(Binary Search Tree),亦称。
二叉排序树或者是一棵空树,或者是具有下列性质的:
(1)若左子树不空,则左子树上所有结点的值均小于它的点的值;
(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)左、右子树也分别为二叉排序树;
(4)没有键值相等的节点。
而且这里题目也强调了第四点,任意两个数字都不同,也就是没有键值相等的点。
分析:
已知条件:后序序列最后一个值为root;二叉搜索树左子树值都比root小,右子树值都比root大。
1、确定root;
2、遍历序列(除去root结点),找到第一个大于root的位置,则该位置左边为左子树,右边为右子树;
3、遍历右子树,若发现有小于root的值,则直接返回false;(不用再去遍历左子树确认是否有大于root的值,因为上一步找到第一个大于root值的位置的时候,就已经确认了左边一定全部小于root)
4、分别判断左子树和右子树是否仍是二叉搜索树(即递归步骤1、2、3)。
AC代码:
public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if (sequence == null || sequence.length == 0) return false; return Vertify1(sequence, 0, sequence.length - 1); } private boolean Vertify1(int[] a, int start, int end) { if (start >= end) return true; // 截止条件可用[4,6,7,5]数据测试 int i = start; while (a[i] < a[end]) { ++i; } for (int j = i; j < end; ++j) { if (a[j] < a[end]) return false; } return Vertify1(a, start, i - 1) && Vertify1(a, i, end - 1); }}
================Talk is cheap, show me the code===================
转载地址:https://liuchenyang0515.blog.csdn.net/article/details/85040853 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月27日 16时02分58秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
JAVA学习笔记10 - 继承
2019-04-30
JAVA学习笔记11 - 接口interface
2019-04-30
JAVA学习笔记12 - 包package
2019-04-30
Android 开发学习笔记 00 - Getting Started
2019-04-30
【学习笔记】Android Activity
2019-04-30
【学习笔记】Android Fragments
2019-04-30
Android使用Retrofit_00_Getting Started
2019-04-30
Android使用Retrofit_01_OAuth2 + GitHub
2019-04-30
Django + REST学习笔记
2019-04-30
【转载】将Ubuntu16.04 中gedit在仅显示一个文件时显示文件名tab
2019-04-30
fstream 对象多次使用时注意clear
2019-04-30
调试 LenaCV 3D Camera (Linux)
2019-04-30
OpenCV杂记 - Mat in C++
2019-04-30
lnmp部署
2019-04-30
location区段
2019-04-30
nginx访问控制、基于用户认证、https配置
2019-04-30