大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
本篇内容主要讲解“Java如何判断一个数组是否为后序遍历结果”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Java如何判断一个数组是否为后序遍历结果”吧!
成都创新互联公司专业为企业提供历城网站建设、历城做网站、历城网站设计、历城网站制作等企业网站建设、网页设计与制作、历城企业网站模板建站服务,10多年历城做网站经验,不只是建网站,更提供有价值的思路和整体网络服务。
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。
思路一:
中序遍历为增长数组,判断是否矛盾
思路二:
如5、7、6、9、11、10、8
代码编写具体思路:
1.找到第一个大于根节点的数,即9,所以9之后的为右子树
2.如果右子树的值都大于根节点8,则符合
3.递归法分别判断是否左子树和右子树都符合这种特点。
package com.lifeibigdata.algorithms.blog; import java.util.Arrays; /** * * 5、7、6、9、11、10、8 * 8 / \ 6 10 / \ / \ 5 7 9 11 */ public class SearchTree { public static void main(String[] args) { // int[] a = {5,7,6,9,11,10,8}; //true int a[] = {7, 4, 6, 5} ; //false System.out.println(searchTree(a,a.length)) ; } static boolean searchTree(int[] a,int length){ if (a == null || length <= 0){ return false; } boolean flag = true; int root = a[length - 1]; int i = 0; while (a[i] < root){ i++; //得到左子树和右子树的分界线,a[i]为右子树第一个 } int j = i; for (;j < length - 1; ++j){ if (a[j] < root){ flag = false; } } if (i > 0){ searchTree(a,i); } if (i < length -1){ searchTree(Arrays.copyOfRange(a,i,length -1),length -i - 1); } return flag; } }
到此,相信大家对“Java如何判断一个数组是否为后序遍历结果”有了更深的了解,不妨来实际操作一番吧!这里是创新互联网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!