输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树:
5
/
2 6
/
1 3
示例 1:
输入: [1,6,3,2,5]
输出: false
示例 2:
输入: [1,3,2,6,5]
输出: true
提示:
数组长度 bool:
def search(prior:int, tail:int):
if prior >= tail:
return True
p = prior
while postorder[p] postorder[tail]: p += 1
return p == tail and search(prior, m - 1) and search(m, tail - 1)
return search(0, len(postorder) - 1)
此题主要做的是我不熟悉的数组形式给出的二叉搜索树。该题算是帮助理解了数组形式的性质。事实上,对于其他两种(先序,中序),这个遍历方法也是很值得借鉴的。下次再遇到遍历数组的二叉树就可以尝试一下了。
此题还有两种非常巧妙的解法,希望今天能看懂并且更新~
