二叉搜索树的后序遍历序列
程序员文章站
2022-05-20 13:52:02
...
BST的后序遍历序列是,对于一个序列S,最后一个元素是x (也就是根),如果去掉最后一个元素的序列为T,那么T满足:T可以分成两段,前一段(左子树)小于x,后一段(右子树)大于x,且这两段(子树)都是合法的后序序列。完美的递归。
class Solution
{
private bool Judge(int[] sequence, int leftIndex, int rightIndex)
{
if (leftIndex >= rightIndex)
return true;
int i = rightIndex - 1;
int j = 0;
while (i > leftIndex && sequence[i] > sequence[rightIndex])
i--;
for (j = i - 1; j >= leftIndex; j--)
if (sequence[j] > sequence[rightIndex])
return false;
return true;
}
public bool VerifySquenceOfBST1(int[] sequence)
{
// write code here
if (sequence.Length == 0)
return false;
return Judge(sequence, 0, sequence.Length - 1);
}
}
上一篇: 二叉树的创建及前中后序遍历和层次遍历
下一篇: 领扣 52. N皇后 II