【LeetCode】二叉搜索树的后序遍历序列 Java 题解

关注

发布于: 56 分钟前

题目描述

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

参考以下这颗二叉搜索树：
     5    / \   2   6  / \ 1   3示例 1：
输入: [1,6,3,2,5]输出: false示例 2：
输入: [1,3,2,6,5]输出: true
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的每日一题是搜索二叉树的知识应用。二叉搜索树具有以下性质：

若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
任意结点的左、右子树也分别为二叉搜索树。

根据题干，需要判断的是给出的数组是不是某二叉搜索树的后序遍历结果。我们只能保证后续遍历的结果:

左子树的所有元素的值 < 根节点的值
右子树的所有元素的值 > 根节点的值

通过代码

class Solution {    public boolean verifyPostorder(int[] postorder) {        int n = postorder.length;        return helper(postorder, 0, n - 1);    }
    public boolean helper(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 && helper(postorder, i, m - 1) && helper(postorder, m, j - 1);    }}

复制代码

总结

二叉树常见考察题目还有构建二叉树，求二叉树的深度等。这类题目需要多练习，多总结，才能更好的掌握。
坚持算法每日一题，加油！

发布于: 56 分钟前阅读数: 3

原文链接:【http://xie.infoq.cn/article/8af0680f80445f1b0025b5a72】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】二叉搜索树的后序遍历序列 Java 题解

题目描述

思路分析

通过代码

总结

HQ数字卡

评论