【剑指offer】-二叉搜索树的后序遍历序列-23/67

简介: 【剑指offer】-二叉搜索树的后序遍历序列-23/67

1. 题目描述

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

2. 题目分析

  1. 题目给的是一个二叉搜索树后序遍历的数组
  2. 二叉搜索树特点:左子树
  3. 后序遍历的特点:最后一个数是根节点(root)
  4. 我们首先验证极端情况:该数组为空,返回false。我们找到数组最后一个数字,也就是根节点,找出该后序遍历序列中左右子树的交叉点
if (sequence == null || sequence.length == 0) {
      return false;
    }
    int root = sequence[sequence.length - 1];
    int i = 0;
    for (i = 0; i < sequence.length - 1; i++) {
      if (sequence[i] > root) {
        break;
      }
    }
  1. 判断右子树是否大于根节点(root)
for (j = i; j < sequence.length - 1; j++) {
      if (sequence[j] < root) {
        return false;
      }
    }
  1. 将左右子树分开,分别进行上述的操作
if (i > 0) {
      left = VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i));
    }
if (j < sequence.length - 1) {
      right = VerifySquenceOfBST(Arrays.copyOfRange(sequence, i, sequence.length - 1));
    }
  1. 关于Arrays.copyOfRange(T[ ] original,int from,int to):将一个原始的数组original,从下标from开始复制,复制到上标to,生成一个新的数组。 注意这里包括下标from,不包括上标to

3. 题目代码

/*
   * 输入一个非空整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
   * Arrays.copyOfRange(T[ ] original,int from,int
   * to):将一个原始的数组original,从下标from开始复制,复制到上标to,生成一个新的数组。 注意这里包括下标from,不包括上标to。
   */
public boolean VerifySquenceOfBST(int[] sequence) {
    if (sequence == null || sequence.length == 0) {
      return false;
    }
    int root = sequence[sequence.length - 1];
    int i = 0;
    for (i = 0; i < sequence.length - 1; i++) {
      if (sequence[i] > root) {
        break;
      }
    }
    int j = i;
    for (j = i; j < sequence.length - 1; j++) {
      if (sequence[j] < root) {
        return false;
      }
    }
    boolean left = true;
    boolean right = true;
    if (i > 0) {
      left = VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i - 1));
    }
    if (j < sequence.length - 1) {
      right = VerifySquenceOfBST(Arrays.copyOfRange(sequence, i, sequence.length - 1));
    }
    return (left && right);
  }


相关文章
|
7月前
|
索引
leetcode106从中序与后序遍历序列构造二叉树刷题打卡
leetcode106从中序与后序遍历序列构造二叉树刷题打卡
43 0
|
7月前
|
Linux
数据结构实验之二叉树八:(中序后序)求二叉树的深度
数据结构实验之二叉树八:(中序后序)求二叉树的深度
|
6月前
|
存储 算法
数据结构和算法学习记录——二叉树的非递归遍历(中序遍历、先序遍历、后序遍历)
数据结构和算法学习记录——二叉树的非递归遍历(中序遍历、先序遍历、后序遍历)
29 0
每日一题:LeetCode-589.N叉树的前序遍历序列构造二叉树
每日一题:LeetCode-589.N叉树的前序遍历序列构造二叉树
剑指offer 34. 二叉搜索树的后序遍历序列
剑指offer 34. 二叉搜索树的后序遍历序列
57 0
|
C++
剑指Offer - 面试题7:重构二叉树 (力扣 - 105、从前序与中序遍历序列构造二叉树)
剑指Offer - 面试题7:重构二叉树 (力扣 - 105、从前序与中序遍历序列构造二叉树)
70 0
剑指offer 58. 二叉搜索树的第k个结点
剑指offer 58. 二叉搜索树的第k个结点
58 0
|
机器学习/深度学习
每日三题-对称二叉树、从前序与中序遍历序列构造二叉树、不同的二叉搜索树
每日三题 对称二叉树 从前序与中序遍历序列构造二叉树 不同的二叉搜索树
100 4
每日三题-对称二叉树、从前序与中序遍历序列构造二叉树、不同的二叉搜索树
|
存储
刷题之完全二叉树的权值和小字辈及根据后序和中序遍历输出先序遍历
刷题之完全二叉树的权值和小字辈及根据后序和中序遍历输出先序遍历
148 0