题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
8
/\
610
/ \/ \
57911
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。
分析:这是一道trilogy的笔试题,主要考查对二元查找树的理解。
在后续遍历得到的序列中,最后一个元素为树的根结点。从头开始扫描这个序列,比根结点小的元素都应该位于序列的左半部分;从第一个大于跟结点开始到跟结点前面的一个元素为止,所有元素都应该大于跟结点,因为这部分元素对应的是树的右子树。根据这样的划分,把序列划分为左右两部分,我们递归地确认序列的左、右两部分是不是都是二元查找树。
参考代码:
usingnamespace std;
///////////////////////////////////////////////////////////////////////
// Verify whether a squence of integers are the post order traversal
// of a binary search tree (BST)
// Input: squence - the squence of integers
//length- the length of squence
// Return: return ture if the squence is traversal result of a BST,
//otherwise, return false
///////////////////////////////////////////////////////////////////////
bool verifySquenceOfBST(int squence[],int
length)
{
if(squence == NULL || length <= 0)
returnfalse;
// root of a BST is at the end of post order traversal squence
int root = squence[length - 1];
// the nodes in left sub-tree are less than the root
int i = 0;
for(; i < length - 1; ++ i)
{
if(squence[i] > root)
break;
}
// the nodes in the right sub-tree are greater than the root
int j = i;
for(; j < length - 1; ++ j)
{
if(squence[j] < root)
return false;
}
// verify whether the left sub-tree is a BST
bool left = true;
if(i > 0)
left = verifySquenceOfBST(squence, i);
// verify whether the right sub-tree is a BST
bool right = true;
if(i < length - 1)
right = verifySquenceOfBST(squence + i, length - i - 1);
return (left && right);
}
分享到:
相关推荐
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果. 8 / \ 6 10 / \ / \ 5...
二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
数据结构C++二叉链表的先序遍历、中序遍历和后序遍历实现
数据结构经典算法,使用C语言编写可以更便于大部分人群阅读,希望大家可以共同进步
已知二叉树的前序和中序遍历,打印后序遍历,采用二叉树的非递归算法,分享给大家~~
二叉搜索树的后序遍历序列,二叉搜索树的后序遍历序列,python,jupyter
有一个整数型列表,判断该列表是否为对应二叉搜索树的后序遍历结果 ''' 二叉搜索树 二叉排序树 二叉查找树 前序遍历 中序遍历 后序遍历 根节点 算法: 1. 找到根节点 2. 遍历序列,找到第一个大于根节点的元素i,则i...
本程序采用非递归方法实现对二叉树的先序、中序、后序遍历.自定义栈和树的结构。
[问题描述] 建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数。 [基本要求] 要求根据读取的元素建立二叉树,能输出各种遍历。 [实现提示] 可通过输入带空格的前序序列建立二叉链表。
已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及先序遍历结果,要求输出其后序遍历结果...
后序遍历二叉树非递归算法的推导及形式化证明,难得的期刊论文资料,对研究二叉树的非递归性遍历有很大帮助
二叉搜索树的后序遍历序列.md
1、用二叉链表作为存储结构,建立一棵二叉树。 2、分别按先序、中序和后序遍历二叉树,输出各遍历序列。 3、编写交换二叉树中所有结点左右孩子
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历。 如果是,则输出Yes,否则输出NO。假设输入的数组的任意两个数字都互不相同。
剑指 Offer 33. 二叉搜索树的后序遍历序列有空看下这个题解,感觉和我的思路不一样面试题33. 二叉搜索树的后序遍历序列(递归分治 / 单调栈,清晰图解)
1024,结点编号1~N)的层次遍历序列和中序遍历序列,输出T从左向右叶子结点以及二叉树先序和后序遍历序列。输入格式输入共三行:第一行是整数n,表示二叉树中的结点数目;第二行有n个整数,表示该二叉树的层次遍历...
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 解法一:递归法 # -*- coding:utf-8 -*- class Solution: def ...