(算法)是否为二叉查找树的后序遍历数组
2023-09-14 08:59:06 时间
题目:
给定一数组,判断它是否为二叉查找树的后序遍历数组
思路:
想想,二叉查找数树的特点,任意根结点大于左子树的所有值,而小于右子树的所有值;
再想想,后序遍历的特点,先遍历左子树,再遍历右子树,最后是根结点;
因此很容易找到根结点,然后遍历数组找出左子树(从左往右比根结点小的),剩下右边的就是右子树,然后判断右子树是否都大于根结点:
如果是,则递归遍历左子树,遍历右子树,如果都满足了,则是某个二叉树的后序遍历数组;
如果不是,则不是。
代码:
#include<iostream> using namespace std; bool IsPostTraverse(int *A,int left,int right){ if(left>=right) return true; else{ int root=A[right]; int idx=left; while(idx<right && A[idx]<root) idx++; int mid=idx; while(idx<right){ if(A[idx]<root) return false; else idx++; } bool IsLeft=IsPostTraverse(A,left,mid-1); bool IsRight=IsPostTraverse(A,mid,right-1); if(IsLeft && IsRight) return true; else return false; } } int main(){ int A[]={3,5,8,13,7,15,10}; int n=sizeof(A)/sizeof(A[0]); cout << IsPostTraverse(A,0,n-1) <<endl; return 0; }
相关文章
- N叉树的前序遍历
- java实现遍历树形菜单方法——OpenSessionView实现
- java实现遍历树形菜单方法——HibernateUtil实现
- Java实现 LeetCode 617 合并二叉树(遍历树)
- Java实现 LeetCode 590 N叉树的后序遍历(遍历树,迭代法)
- Java实现 LeetCode 559 N叉树的最大深度(遍历树,其实和便利二叉树一样,代码简短(●ˇ∀ˇ●))...
- Scala元组数据的遍历
- 剑指 Offer 53 - II. 0~n-1中缺失的数字 -遍历
- 865. 具有所有最深节点的最小子树-dfs遍历
- 常用的遍历算法
- 【Linux 内核 内存管理】物理分配页 ⑤ ( get_page_from_freelist 快速路径调用函数源码分析 | 遍历备用区域列表 | 启用 cpuset 检查判定 | 判定脏页数量 )
- 算法实验-二叉树的创建和前序-中序-后序-层次 遍历
- Map集合遍历的四种方式理解和简单使用
- 重拾算法(3)——用458329个测试用例全面测试二叉树和线索二叉树的遍历算法
- DFS 算法模板——二叉树的遍历非递归写法要会,排列组合的一定要自己画一颗树,变量i和当前遍历层数计数的start_index要注意区分
- 算法 dfs —— 将二叉树 先序遍历 转为 链表
- 最长绝对文件路径——算法面试刷题1(google),字符串处理,使用tree遍历dfs类似思路
- 树的遍历 迭代算法——思路:初始化stack,pop stack利用pop的node,push new node to stack,可以考虑迭代一颗树 因为后序遍历最后还要要访问根结点一次,所以要访问根结点两次是难点
- 重新整理数据结构与算法(c#)—— 图的深度遍历和广度遍历[十一]