题解 | #二叉搜索树的后序遍历序列 java#

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

https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd

import java.util.*;
public class Solution {
    public boolean isAfterOrder(int []sequence, int l, int r) {
        // foolproof
        if (l >= r) return true;

        int root = sequence[r];

        int j = r - 1;
        // get right range
        while (j >= 0 && sequence[j] > root) {
            j--;
        }
        // check right range is litter than root
        for (int i = l; i <=j; i++) {
            // return false
            if (sequence[i] > root) return false;
        }
        // l--> j,  j+1 --> r-1
        return isAfterOrder(sequence, l, j) && isAfterOrder(sequence, j+1, r-1);
    }
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        int left = 0;
        int right = sequence.length - 1;

        return isAfterOrder(sequence, left, right);
    }
}

解题思路:

如果这个序列array是一个二叉搜索树的后续遍历,那么必定会满足4个条件:

  1. root一定在序列末尾,array[len-1]
  2. 在中间的某个节点 j可以满足 array[0:j+1] < root 这部分区域是左子树的区域; array[j+1: len-1] > root // 题干中提到这里的每个元素都不相同, 所以不存在等于的情况;
  3. 由于二叉树是递归的结构; 因此 在 array[0:j+1] 和 array[j+1,len-1]区域已经可以再次划分出满足条件的左右子树的区域

因此在写的时候, 可以先做一个区域中找出 j的位置, 然后在检查另一个区域是否满足条件

note_coding 文章被收录于专栏

记录自己的解题思路, 欢迎评价

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务