剑指Offer:二叉搜索树的后序遍历

题目

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

1
2
3
4
5
     8
/ \
6 10
/ \ / \
5 7 9 11

分析

首先我们要知道后序遍历的特点:在后序遍历中,最后一个数字树的根节点。数组中的前面的数字可以分为两部分:第一部分是树的左子树的节点的值,他们都比根节点的值小;第二部分是右子树的值,他们都比根节点的值大。

以数组5,7,6,9,11,10,8为例。后序遍历结果的最后一个数字8就是根节点的值。在这个数组中,前3个数字5,7,6都是比8小,是节点8的左子树的节点。后3个数字都比8大,是节点8的右子树节点。

我们接下来用同样的方法来确定数组中的每一部分对应的子树的结构。这个其实就是一个递归的过程。对于序列5,7,6最后一个节点6是左子树的根节点。数字5比6小,是节点6的左子树。数字7比6大,是节点6的右子树。序列9,11,10同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence, int begin, int end) {
if (end <= begin)
return true;

int root = sequence[end];
//在二叉搜索树中左子树节点的值小于根节点的值
int i = begin;
while (i < end) {
if (sequence[i] > root)
break;
i ++;
}
// 在二叉搜索树右子树节点的值大于根节点的值
int j = i;
while (j < end-1) {
if (sequence[j] < root)
return false;
j ++;
}
return VerifySquenceOfBST(sequence, begin, i-1) && VerifySquenceOfBST(sequence, i, end-1);
}

public boolean VerifySquenceOfBST(int [] sequence) {
int len = sequence.length;
if (sequence == null || len == 0)
return false;

return VerifySquenceOfBST(sequence, 0, len-1);
}
}
有收获再赞赏哦🤭
------ 本文结束感谢您的阅读-------------
0%