/*************************************************************
题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历
的结果。如果是则返回true,否则返回false。假设输入的数组的任意两
个数字互不相同。
**************************************************************/
#include<stdio.h>
bool verifysequenceOfBST(int* sequence, int length)
{
if(!sequence || length<=0)
return false;
int root = sequence[length-1];
int i;
for(i=0; i<length-1; ++i)
{
if(sequence[i]>root)
break;
}
int j = i;
for(;j<length-1; ++j)
{
if(sequence[j]<root)
return false;
}
bool bLeft = true;
if(i>0)
bLeft = verifysequenceOfBST(sequence,i);
bool bRight = true;
if(i<length-1)
bRight = verifysequenceOfBST(sequence+i,length-i-1);
return (bLeft && bRight);
}
int main()
{
int arr[7] = {5,7,6,9,11,10,8};
if(verifysequenceOfBST(arr,7))
printf("yes!\n");
else
printf("no!\n");
return 0;
}
相关题目:
输入一个整数数组,判断该数组是不是某二叉搜索树的前序遍历的结果。
举一反三:
如果面试是要求处理一颗二叉树的遍历序列,我们可以先找到二叉树的根节点,
再基于根节点把整棵树的遍历序列拆分成左子树对应的子序列和右子树对应的
子序列,接下来在递归地处理这两个子序列。
==参考剑指OFFER
分享到:
相关推荐
二叉搜索树的后序遍历序列,二叉搜索树的后序遍历序列,python,jupyter
二叉搜索树的后序遍历序列.md
剑指 Offer 33. 二叉搜索树的后序遍历序列有空看下这个题解,感觉和我的思路不一样面试题33. 二叉搜索树的后序遍历序列(递归分治 / 单调栈,清晰图解)
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历。 如果是,则输出Yes,否则输出NO。假设输入的数组的任意两个数字都互不相同。
剑指Offer(Python多种思路实现):二叉搜索树的后序遍历序列 面试33题: 题:二叉搜索树的后序遍历序列 题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设...
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树: 5 / \ 2 6 / \ 1 3 示例 1: 输入:...
假设输入的数组的任意两个数字都互不相同扩展:判断数组是不是某BST的前序遍历结果使用递归,利用后序遍历的性质bool dfs(int left, int rig
1.最后一个节点为根节点 2.左边的节点全部要小于根,右边的节点全部要大于根,因此数组可以分成两个区间,前半部 3.找到两个区间的分割点,判断是否两个区间是否符
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 解法一:递归法 # -*- coding:utf-8 -*- class Solution: def ...
//cutIndex左边的结点都是根节点的左子树,右边的结点都是根节点的右子树return verify(postorder, first, cutIndex
有一个整数型列表,判断该列表是否为对应二叉搜索树的后序遍历结果 ''' 二叉搜索树 二叉排序树 二叉查找树 前序遍历 中序遍历 后序遍历 根节点 算法: 1. 找到根节点 2. 遍历序列,找到第一个大于根节点的元素i,则i...
[问题描述] 如果给出了遍历二叉树的前序序列和中序序列,则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。...(3)对该二叉树进行后序遍历,输出后序遍历序列。 (4)用凹入法输出该二叉树。
构造二叉树根据前序与中序遍历序列构造二叉树根据先序遍历构造二叉搜索树根据中序与后序遍历序列构造二叉树根据前序与后序遍历序列构造二叉树 二叉树的遍历顺序及方法可参考之前写过的二叉树的遍历(JAVA递归和非...
1.在二叉搜索树中插入节点 2.前序、中序、后序遍历该二叉搜索树,写出遍历序列 3.输出二叉搜索树的深度、节点数目、叶子节点数目 4.退出
二叉搜索树(排序二叉树),树的遍历(前序、中序、后序)【数据结构和算法入门7】
调整数组顺序使奇数位于偶数之前.py 链表中倒数第k个节点.py 链表中环的入口节点.py 反转链表.py 合并两个排序的链表.py 树的子结构.py ...二叉搜索树的后序遍历序列.py 二叉树中和为某一值的路径.py
二叉树、二叉搜索树的构建,前序、中序、后序的 递归和非递归遍历;前序中序序列构建二叉树……
1.在二叉搜索树中插入节点 2.前序、中序、后序遍历该二叉搜索树,写出遍历序列 3.输出二叉搜索树的深度、节点数目、叶子节点数目 4.退出
33.二叉搜索树的后序遍历序列 Tree 常考 34.二叉树中和为某一值的路径 Tree 35.复杂链表的复制 Linked List 36.二叉搜索树与双向链表 Linked List 37.序列化二叉树 Tree 关注 38.字符串的排列 String 关注 39....
从中序与后序遍历序列构造二叉树 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的...