【算法】【二叉树模块】求二叉树中最大搜索二叉子树，返回头结点

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
求二叉树中最大的二叉子树
如图所示二叉树：

该二叉树的最大搜索二叉子树结构为：

返回节点6即可

解决方案

1、后续遍历二叉树
2、每一次的遍历都返回四个信息：
· 当前节点为根节点的子树中最大的搜索二叉树
· 当前节点为根节点的子树中最大搜索二叉树的节点个数
· 当前节点为根节点的子树中最大值
· 当前节点为根节点的子树中最小值
3、返回上一层时判断当前节点为根节点的子树是否是搜索二叉树，如果是，则将信息更新后返回上一层，如果不是则判断左右子树谁size更大，谁就是当前的最大搜索子树，更新record返回上一层即可.

代码编写

java语言版本

    public static MyTreeNode getBST(MyTreeNode root){
        if (root == null){
            return null;
        }
        int[] record = new int[3];
        return process(root, record);
    }


    /**
     * 每一个节点遍历都要返回四个数据：
     * 1、以该节点为root的最大搜索二叉树节点的root节点
     * 2、搜索二叉子树节点数量
     * 3、搜索二叉子树的最大值
     * 4、搜索二叉子树的最小值
     * @param root
     * @param record
     * @return
     */
    private static MyTreeNode process(MyTreeNode root, int[] record) {
        if (root == null){
            record[0] = 0;
            record[1] = Integer.MIN_VALUE;
            record[2] = Integer.MAX_VALUE;
            return null;
        }
        MyTreeNode leftMaxRoot = process(root.getLeft(), record);
        int leftSize = record[0];
        int leftMax = record[1];
        int leftMin = record[2];
        MyTreeNode rightMaxRoot = process(root.getRight(), record);
        int rightSize = record[0];
        int rightMax = record[1];
        int rightMin = record[2];
        if (leftMaxRoot == root.getLeft() && rightMaxRoot == root.getRight()
                && leftMax < root.getData() && rightMin > root.getData()){
            // 自己就是一颗二叉树
            record[0] = leftSize + rightSize + 1;
            record[1] = rightMax == Integer.MIN_VALUE ? root.getData() : rightMax;
            record[2] = leftMin == Integer.MAX_VALUE ? root.getData() : leftMin;
            return root;
        }else {
            // 比较左边和右边哪个大
            if (leftSize >= rightSize){
                record[0] = leftSize;
                record[1] = leftMax;
                record[2] = leftMin;
                return leftMaxRoot;
            }else{
                record[0] = rightSize;
                record[1] = rightMax;
                record[2] = rightMin;
                return rightMaxRoot;
            }
        }
    }

    public static void main(String[] args) {
        MyTreeNode root = CommonUtils.getSearchMyTreeNode();
        MyTreeNode node1 = new MyTreeNode(1);
        MyTreeNode node9 = new MyTreeNode(9);
        node1.setRight(root);
        node1.setLeft(node9);
        PrintTreeDirect.myPrint(node1);
        getBST(node1);
    }

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

1、思路来源
二叉树中用得最多的思想就是将同一个问题通过递归“问到”每一个子树，怎么理解这句话呢？当前问题就是求二叉树中最大搜索二叉子树，那么把这个问题问到每一个子树，以该题为例，首先问到1问子树9和子树6是否存在最大搜索二叉子树，9和6判断自己是否能够成为最大子树跟自己判断是否能够成为最大子树是一样的逻辑，因此自己需要什么信息，9和6就需要什么信息，那么1需要9中最大子树的头结点并且还要知道节点数（第二个信息），知道以后还要判断自己是否也能成为最大子树，所以需要9提供最大值（第三个信息）和最小值（第四个信息），6也是同理
2、注意要点：
这里需要注意一下null的返回判断，如果遍历到null时，说明null值天然支持父节点成为二叉子树，因此节点数为0，最大值尽可能的小，最小值尽可能的大，让父节点符合条件。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！