dede怎么做双语网站,wordpress打开最快的网站,深圳做网站网络公司有哪些,微商城手机网站设计公司二叉树后续遍历序列校验 题目#xff1a;输入一个整数数组#xff0c;判断改数组是否是某个二叉搜索树的后续遍历结果#xff0c;如果是返回true否则false#xff0c;假设输入数组的任意两个数字不相同。 例如输入{5,7,6,9,11,10,8}则返回true#xff0c;因为这个整数序列…二叉树后续遍历序列校验 题目输入一个整数数组判断改数组是否是某个二叉搜索树的后续遍历结果如果是返回true否则false假设输入数组的任意两个数字不相同。 例如输入{5,7,6,9,11,10,8}则返回true因为这个整数序列是如下图二叉搜索树的后续遍历结果 如果输入{7,46,5}没有哪个二叉搜索树后续遍历结果是这个序列。 我们必须先知道二叉搜索树的一些基本特性在之前的文章二叉查找树实现原理对二叉搜索树进行的详细的说明已经案例分析在二叉搜索树中如下两个性质 对于树中每个节点X左子树中所有项小于X中的项而右子树中的所有元素都大于X中的项目 分析 因为是后续遍历因此根节点在末尾左移8 是根数组分两部分前面左子树节点比如比根节点小后面右子树节点必然比根节点大第二个7,46,5 是中间小两边大不存在这种情况判断完左右子树都符合要求则分别将左右子树当成完整的树依次执行以上步骤递归实现。如上分析有如下实现
/*** 判断给定序列是否二叉查找树后续遍历* author liaojiamin* Date:Created in 18:22 2021/4/2*/
public class ValidateRightFirst {public static boolean validateRightList(int[] binaryNodeList){if(binaryNodeList null || binaryNodeList.length 1){return false;}return validateRightList(binaryNodeList, 0, binaryNodeList.length-1);}public static boolean validateRightList(int[] binaryNodeList, int start, int end){if(binaryNodeList null|| start end){return false;}int root binaryNodeList[end];int middlePosition 0;for (int i start; i end-1; i) {if(binaryNodeList[i] root){middlePosition i;break;}}for(int i middlePosition; i end-1;i ){if(binaryNodeList[i] root){return false;}}boolean left true;if(middlePosition 0){left validateRightList(binaryNodeList, start, middlePosition-1);}boolean right true;if(middlePosition end -1){right validateRightList(binaryNodeList, middlePosition, end-1);}return left right;}public static void main(String[] args) {int[] binaryNodeList {5,7,6,9,11,10,8};System.out.println(validateRightList(binaryNodeList));}
}上一篇数据结构与算法-- 广度优先打印二叉树 下一篇数据结构与算法-- 二叉树中和为某一值的路径
