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

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

题目:

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

思路：

在后序遍历得到的序列中，最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分:第一部分是左子树结点的值，它们都比根结点的值小；第二部分是右子树结点的值，它们都比根结点的值大。

代码如下：

bool VerifyBST(int squence[], int length)
{
 if (squence==NULL||length<=0)
  return false;
 //序列中最后一个数字是根结点的值
 int root=squence[length-1];
 //二叉搜索树中左子树的结点值小于根结点
 int i=0;
 for ( ; i<length-1; i++)
 {
  if (squence[i]>root)
   break;
 }
 //二叉搜索树中右子树的结点值大于根据点
 int j=i;//i为右子树的根结点值
 for( ; j<length-1; j++)
 {
  if (squence[j]<root)
   return false;
 }
 //判断左子树是不是二叉搜索树
 bool left=true;
 if (i>0)
 {
  left=VerifyBST(squence,i);
 }
 //判断右子树是不是二叉搜索树
 bool right=true;
 if (j<length-1)
 {
  right=VerifyBST(squence,length-1-i);
 }
 return (left&&right);
}

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在JAVA中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目

本文永久更新链接地址：