二叉搜索树的后序遍历序列
Hard;
1. Link
2. 描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。(ps:我们约定空树不是二叉搜素树)
示例1
输入:
[4,8,6,12,16,14,10]
复制返回值:
true
3. 思路
Post-order traversal 特性:post-order traveral 的result 从右到左的打印相对于是pre-order traversal的打印的结果往相反顺序打印,即先打印右边再打印左边
举个例子
5 / \ 3 7 / \ / \ 1 2 6 8 pre-order: 5, 3, 1, 2, 7, 6, 8 post-order: 1,2,3,6,8,7,5 inverse post-order: 5, 7, 8, 6, 3, 2,1
所以用post-order检查BST时,从右往左遍历array,并且用个stack记录当前最大值
当发现array[i] 的值< stack top的最大值,就不断把stack的最大值pop出来直到找到小于array[i]的值为止, 这个过程相对于遍历完右子树,返回上一层找左子树。
当往左遍历时如果发现node的值> 当前最大值,即左子树的值> parent 或 右子树的值,那么就return False
Time: 遍历每个array的值 O(n) , 因为push的个数= pop的个数,并非每次pop的都是O(n), 所以实际上是O(n) for popping +O(n) for iterating array = O(n)
Space: O(n)
Note: pre-order traversal 和 反转过来的post-order traversal 在树的遍历方向上是对称/相反的,pre-order traversal 从左往右, post-order traversal 反转顺序后是从右往左 而in-order traversal 相对于把tree 当成list一样平铺开来再打印
4. Coding
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
#idea:
# in post-order BST, the last node in sequence = root node
#1. find the root node at the end of seq and iterate node before root node to find the
# start from right to left, find the first node with val < root val
#
#then partition subarray by this boundary to get left subtree and right subtree
# and pass the root val to the recursion
# For left subtree, find the root of left subtree and find the boundary
# of element < root of left and <parent root, if find any element > parent root
# return False
# similar to left subtree, right subtree do the same thing
#
# post-order traversal 的特点是
# 从右往左iterate array相对于 current-node-> right node->left node的方向的遍历
# 相当于和pre-order的对称
#
#
if not sequence:
return False
max_val = float('inf')
min_val = -float('inf')
stack = [min_val]
for i in range(len(sequence)-1, -1, -1):
if sequence[i] > max_val:
return False
# pop the right subtree values
# and find the node of left subtree
while sequence[i] < stack[-1]:
max_val = stack.pop(-1)
stack.append(sequence[i])
return True
Last updated
Was this helpful?