当前位置: 代码迷 >> 综合 >> 二叉搜索树后序序列
  详细解决方案

二叉搜索树后序序列

热度:81   发布时间:2024-01-16 23:50:50.0

1.题意

给定一个序列,判断此序列是否是一个二叉搜索树的后续遍历序列

  • 二叉搜索树:左子树都比根节点小,右子树都比根节点大

2.分析

  • 后序遍历序列,最后一个是根节点

  • 比根节点小的的是左子树部分,可以无左子树

  • 剩下的是右子树部分,必须比根节点大,可以无右子树

  • 递归检查序列的每段,直到检查段长度为1(到叶子节点)

3.代码

bool isOrderBST(int* a, int length)
{if(a==NULL || length<=0)return false;int root = a[length-1];int leftEnd = 0;while(leftEnd<length-1 && a[leftEnd]<root)leftEnd++;//此时leftEnd等于左子树长度,a[leftEnd]指向右子树第一个for(int i=leftEnd; i<length-1; i++){if(a[i] < root)return false;//右子树小于根节点,不符合BST定义}bool left = true;if(leftEnd > 0)//有左子树left = isOrderBST(a, leftEnd);if(left == false)return false;//左边不符合,没必要接着判断右边,剪枝bool right = true;if(leftEnd < length - 1)//有右子树right = isOrderBST(a+leftEnd, length-1-leftEnd);return right;
}

  相关解决方案