只做嵌入式 2021-11-11 22:12 采纳率: 42.9%
浏览 21
已结题

二叉搜索树的后序遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。

数据范围: 节点数量 0 \le n \le 10000≤n≤1000 ,节点上的值满足 1 \le val \le 10^{5}1≤val≤10
5
,保证节点上的值各不相同
要求:空间复杂度 O(n)O(n) ,时间时间复杂度 O(n^2)O(n
2
)
提示:
1.二叉搜索树是指父亲节点大于左child节点,但是小于右child节点。
2.该题我们约定空树不是二叉搜索树
3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历

img

  • 写回答

1条回答 默认 最新

  • 从善若水 5G/6G通信领域优质创作者 2021-11-11 22:16
    关注
    
    public class Solution {
        public boolean VerifySquenceOfBST(int [] sequence) {
            if(sequence.length==0)
                return false;
            if(sequence.length==1)
                return true;
            return ju(sequence, 0, sequence.length-1);
            
        }
        
        public boolean ju(int[] a,int star,int root){
            if(star>=root)
                return true;
            int i = root;
            //从后面开始找
            while(i>star&&a[i-1]>a[root])
                i--;//找到比根小的坐标
            //从前面开始找 star到i-1应该比根小
            for(int j = star;j<i-1;j++)
                if(a[j]>a[root])
                    return false;;
            return ju(a,star,i-1)&&ju(a, i, root-1);
        }
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 11月19日
  • 已采纳回答 11月11日
  • 创建了问题 11月11日

悬赏问题

  • ¥15 ecplise在连接数据库时显示加载驱动成功但是数据库连接失败
  • ¥15 visionmaster启动失败,提示为“机器不满足授权而被禁用”
  • ¥50 用logisim设计16位单时钟周期cpu
  • ¥15 IDEA中圈复杂度如何具体设置
  • ¥50 labview采集不了数据
  • ¥15 请上面代码做什么处理或什么混淆
  • ¥15 英雄联盟自定义房间置顶
  • ¥15 W5500网线插上无反应
  • ¥15 如何用字典的Key,显示在WPF的xaml中
  • ¥15 weautomate读取Excel表格信息然后填写到网页一直报错,如何解决?