数据结构与算法-- 二叉树后续遍历序列校验

喜欢ヅ旅行 2022-11-16 10:55 136阅读 0赞

#### 二叉树后续遍历序列校验 ####

*  题目：输入一个整数数组，判断改数组是否是某个二叉搜索树的后续遍历结果，如果是返回true否则false，假设输入数组的任意两个数字不相同。
 *  例如输入\{5,7,6,9,11,10,8\}则返回true，因为这个整数序列是如下图二叉搜索树的后续遍历结果：  
    ![在这里插入图片描述][20210406172759375.png]
 *  如果输入\{7,4，6,5\}没有哪个二叉搜索树后续遍历结果是这个序列。
 *  我们必须先知道二叉搜索树的一些基本特性，在之前的文章：[二叉查找树实现原理][Link 1]对二叉搜索树进行的详细的说明，已经案例分析，在二叉搜索树中如下两个性质：
    
     *  对于树中每个节点X，左子树中所有项小于X中的项
     *  而右子树中的所有元素都大于X中的项目
 *  分析：
    
     *  因为是后续遍历，因此根节点在末尾，左移8 是根
     *  数组分两部分，前面左子树节点比如比根节点小
     *  后面右子树节点必然比根节点大
     *  第二个7,4，6,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));
        }
    }

[上一篇：数据结构与算法-- 广度优先打印二叉树][--]  
[下一篇：数据结构与算法-- 二叉树中和为某一值的路径][-- 1]

[20210406172759375.png]: /images/20221022/04c35f8497c44611b21ed5e375aa315d.png
[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/111231303
[--]: https://blog.csdn.net/liaojiamin0102/article/details/115465861
[-- 1]: https://blog.csdn.net/liaojiamin0102/article/details/116923539