题目：二叉搜索树的后台遍历序列。输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。
解题思路：在后序遍历得到的序列中，最后一个数字是树的根节点的值。数组中前面的数字可以分为两部分：第一部分是左子树结点的值，它们都比根结点的值小；第二部分是右子树结点的值，他们都比根结点的值大。
C#实现：
|
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 static bool VerifySquenceOfBST(int[] sequence, int start, int end)
{
if (sequence == null || start < 0 ||start > end)
return false;
int root = sequence[end];
// 在二叉搜索树中左子树的结点小于根结点
int i = start;
for (; i < end; i++)
if (sequence[i] > root)
break;
// 在二叉搜索树中右子树的结点大于根结点
int j = i;
for (; j < end; j++)
if (sequence[j] < root)
return false;
// 判断左子树是不是二叉搜索树
bool left = true;
if (i > start)
left = VerifySquenceOfBST(sequence, start, i-1);
// 判断右子树是不是二叉搜索树
bool right = true;
if (i < end)
right = VerifySquenceOfBST(sequence, i, end-1);
return left && right;
}
|
Java实现：
|
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
|
public static boolean verifySquenceOfBST(int[] sequence, int start, int end){
if(sequence == null || start < 0 || start > end)
return false;
int root = sequence[end];
// 在二叉搜索树中左子树的结点小于根结点
int i = start;
for (; i < end; i++)
if (sequence[i] > root)
break;
// 在二叉搜索树中右子树的结点大于根结点
int j = i;
for (; j < end; j++)
if (sequence[j] < root)
return false;
// 判断左子树是不是二叉搜索树
boolean left = true;
if (i > start)
left = verifySquenceOfBST(sequence, start, i-1);
// 判断右子树是不是二叉搜索树
boolean right = true;
if (i < end)
right = verifySquenceOfBST(sequence, i, end-1);
return left && right;
}
|
Python：
|
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
32
33
34
35
36
37
38
|
@staticmethod def verifySequenceOfBST(sequence, start, end):
"""
二叉搜索树的后台遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同
:param sequence: 列表
:param start: 开始下标
:param end: 结束下标
:return:
"""
if sequence == None or start < 0 or start > end:
return False
root = sequence[end]
# 在二叉搜索树中左子树的结点小于根结点
i = start
for i in range(start, end):
if sequence[i] > root:
break
# 在二叉搜索树中右子树的结点大于根结点
for j in range(i, end):
if sequence[j] < root:
return False
# 判断左子树是不是二叉搜索树
left = True
if i > start:
left = BinaryTree.verifySequenceOfBST(sequence, start, i-1)
# 判断右子树是不是二叉搜索树
right = True
if i < end:
right = BinaryTree.verifySequenceOfBST(sequence, i, end-1)
return left and right
|
本文转自 许大树 51CTO博客，原文链接：http://blog.51cto.com/abelxu/1975465，如需转载请自行联系原作者