二叉搜索树的后遍历序列（Sword Finger Offer33）

主题描述: 输入一个整数数组，以确定该数组是否是遍历二叉搜索树的结果.

如果返回true，否则返回false. 假设输入数组中的任何两个数字互不相同.

例如，输入{5,7,6,9,11,10,8}并返回true.

输入{7,4,6​​,5}并返回false.

在回答这个问题之前，让我们熟悉二叉搜索树的概念:

注意: 二进制搜索树二叉排序树 遍历，二进制搜索树（BST）和二进制排序树是同一概念

二叉搜索树:

1. 如果左子树不为空，则左子树上所有节点的值都相同

小于或等于其根节点的值；

2. 如果右子树不为空，则右子树上所有节点的值都相同

大于或等于其根节点的值；

3. 左右子树也是二叉搜索树.

4. 相等的情况只能出现在左或右子树中

一侧.

由于二分搜索树的中阶遍历从小到大二叉排序树 遍历，所以也被称为

二进制排序树.

思考: 在通过后序遍历获得的序列中，最后一个数字是树的根节点的值. 数组中的前一个数字可以分为两部分:

第一部分是左子树节点的值，它们都小于根节点的值；第二部分是右子树节点的值，它们都大于根节点的值；

考虑一下，我们可以在程序中提出递归.

根据根节点的值划分左右子树节点，并以相同方式处理左右子树.

代码非常清晰，请仔细阅读代码！ ！

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-220706-1.html