题目
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树:
1
2
3
4
5 5
/ \
2 6
/ \
1 3示例 1:
1
2 输入: [1,6,3,2,5]
输出: false示例 2:
1
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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
递归
根据后序遍历以及二叉搜索树的特性很容易分析出,一棵树的后序遍历序列的最后一个元素是根节点的值,该值必须能够将其前面的数组分成两部分,左半部分值小于它,右半部分值大于它。
所以我们递归地对每一棵树进行判断,取根节点元素,向左找到第一个小于它的元素,继续向左判断每个元素是否小于根节点。
但是这样的做法很容易看出来需要重复遍历很多节点,如果我们能记住每一次递归的根节点就容易很多。
单调栈
从二叉搜索树的节点含义来看上述操作,从后序遍历尾部开始向前遍历,相当于从根节点开始,此时是后序遍历的逆序,即根->右->左的顺序,而我们如何判断一棵树是否为二叉搜索树呢?即一个根节点的右子节点必须大于该根节点,左子节点必须小于该根节点。
我们称根->右->左的顺序为 reverse postorder,那么它会首先走一条只有右子节点的路径,每到达一个节点就直接访问,因此访问顺序是递增的,直到叶子节点,此时该节点的后继节点必定小于当前节点,也就是说它是某个节点的左子节点,而这个左子节点必须小于它的父节点,因此我们需要找到这个父节点。
我们知道当前还未遍历的所有剩余节点都是某个节点的左子节点,因此可以用相同的规则来判断。因此我们要做的就是设计一种方法来保存每个根节点。
最容易想到的方法就是栈,用栈来存储根节点,因为我们优先访问右子节点,需要利用根节点来访问左子节点。
我们首先将递增序列全部入栈,接下来遇到小于栈顶元素(当前根节点)的元素时,弹栈并更新当前根节点,该元素的父节点一定是大于该元素的,因此,栈空或者直到栈顶元素小于该元素时,我们知道我们刚刚更新的根节点就是该节点的父节点,因此用该父节点对以该元素为根节点的树进行判断,即将该元素入栈,用当前根节点对后续节点进行判断。
1 | class Solution { |
感觉逻辑还是不是很清晰,再捋一捋。