首页 > 代码库 > 判断一个数组是否是一个二叉排序树的后序遍历结果
判断一个数组是否是一个二叉排序树的后序遍历结果
比如给出数组[5,7,6,9,11,10,8]判断其是否为二叉排序树的后序遍历结果，也就是能不能画出一个二叉排序树使其的后序遍历结果与这个数组相同，若可以返回true，不可以返回false。
代码：
int is_valid(int *data, int n){ if(data=http://www.mamicode.com/=NULL)return 0; int left=1; int right=1; int i=0; int j; int root=data[n-1]; while(data[i]<root){ i++; } for(j=i+1;j<n-1;j++){ if(data[j]<root){ return 0; } } if(i>0){ left=is_valid(data, i); } if(j<n-1){ right=is_valid(data, j); } return (left && right);}
思路：
数组的最后一个数肯定为根节点，那么从头遍历，找到第一个小于根节点和大于根节点数的交界处，然后继续遍历从这个数开始到根节点之间的数，若存在小于根节点的数（理论上从交界点往后到根节点之前的数都应该大于根节点，因为它们处在根节点的右子树上。）那么返回false。
然后递归。。。
判断一个数组是否是一个二叉排序树的后序遍历结果
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。