二叉搜索树的后序遍历序列

Posted on In Views: Waline: Views: Symbols count in article: 536 Reading time ≈ 1 mins.

题解方法

  • 递归

递归

二叉搜索树定义： 左子树中所有节点的值 < 根节点的值；右子树中所有节点的值 > 根节点的值；其左右子树也分别为二叉搜索树。

  1. 找到根节点，划分左右子树区间。
  2. 根据二叉搜索树定义，验证左右子树区间。
  3. 递归分别验证左右子树。

核心代码

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean verify(int start, int end) {
	if (start >= end) {
		return true;
	}
	int root = postorder[end];
	int idx = start;
	while (idx < end && postorder[idx] < root) {
		idx++;
	}
	int mid = idx;
	while (idx < end && postorder[idx] > root) {
		idx++;
	}
	if (idx != end) {
		return false;
	}
	return verify(start, mid - 1) && verify(mid, end - 1);
}

题目来源

二叉搜索树的后序遍历序列 - 力扣（LeetCode）