Interview----判断整数序列是否是二叉搜索树的后序遍历结果

题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。

如果是返回true，否则返回false。

例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：

8

/ \

6 10

/ \ / \

5 7 9 11

因此返回true。

如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回 false。

思路：

抓住二叉搜索树的两个重要的性质：

1. 左子树所有节点的值 <= 当前节点 <= 右子树的所有节点的值

2. 左右子树都是一棵搜索树

关于二叉搜索树的详细分析可参考： http://blog.csdn.net/shoulinjun/article/details/18449445

性质 1 对应于后序遍历就是：后序遍历左边第一段的值 <= root <= 第二段的值。 root 就是最后一个节点。

性质 2 通过递归调用即可。

bool IsBST(vector<int>::iterator begin, vector<int>::iterator end)

{

  if (end - begin < 3)

    return true;

  //左子树 小于当前节点，小于右子树

  vector<int>::iterator left_end = begin;

  for(; *left_end <= *(end-1); ++ left_end); //use root as sentinel

  for(vector<int>::iterator it = left_end+1; it != end; ++it)

    if (*it < *(end-1))

	  return false;

  //left tree is a BST, and right tree as well

  if (IsBST(begin, left_end) && IsBST(left_end, end-1))

    return true;

  else

    return false;

}

巴特西

Interview----判断整数序列是否是二叉搜索树的后序遍历结果

最新文章

热门文章