1. 题目描述

给定二叉树的头节点head，返回此树中最大的二叉搜索子树的大小

2. 测试案例

树为空
树不空

3. 最佳思路

前置知识：第4步中的常用手法
在第4步中，关于递归边界：

如果好设置跳出递归的边界信息时就直接设置：if(root == null) return new Node(设置信息);

如果不好设置跳出递归的边界信息时就返回null：if(root == null) return null;。其处理逻辑如下：

小细节：

关于info字段设置的先后顺序：与x有关无关不会影响字段值的放在前面编写，会影响的放在后面。

关于与x有关无关的编写的先后顺序：编写x有关无关的代码时，将无条件的代码放在前面，将有条件的代码放在后面。如果都有条件或都无条件则无先后顺序。

4. 代码


public class Main {

    static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    static class Info {
        public boolean isBST;
        public int maxBSTSubtreeSize;
        public int max;
        public int min;

        public Info(boolean isBST, int maxBSTSubtreeSize, int max, int min) {
            this.isBST = isBST;
            this.maxBSTSubtreeSize = maxBSTSubtreeSize;
            this.max = max;
            this.min = min;
        }
    }

    public static void main(String[] args) {
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(7);
        System.out.println(largestBSTSubtree(root));
    }

    // 返回此树中最大的二叉搜索子树的大小
    public static int largestBSTSubtree(Node head) {
        if (head == null) {
            return 0;
        }
        return process(head).maxBSTSubtreeSize;
    }

    public static Info process(Node root) {
        /* 0. 边界条件 */
        if (root == null)
            return null;  // 因为：return new Info(true, 0, 不好设置， 不好设置); 所以只能返回null，然后后面每次用到leftInfo 、rightInfo 时都判空即可。

        /* 1. 左 */
        Info leftInfo = process(root.left);

        /* 2. 右 */
        Info rightInfo = process(root.right);

        /* 3. 根：实例化Info对象，并将其值设置正确，最后返回该对象即可 */
        // (1) 实例化Info对象
        Info info = new Info(false, 0, 0, 0);
        // (2) 设置max、min的值
        info.min = Math.min(root.value, leftInfo == null ? root.value : leftInfo.min); // 取 左子树上的最大值与当前结点的值 中小的那个
        info.max = Math.max(root.value, rightInfo == null ? root.value : rightInfo.max);
        // (3) 设置maxBSTSubtreeSize、isBST的值
        //   ① 与x无关
        info.maxBSTSubtreeSize = Math.max(leftInfo == null ? 1 : leftInfo.maxBSTSubtreeSize,
                rightInfo == null ? 1 : rightInfo.maxBSTSubtreeSize);
        info.isBST = false;
        //   ② 与x相关
        if ((leftInfo == null ? true : leftInfo.isBST) // 左子树为二叉搜索子树
                && (rightInfo == null ? true : rightInfo.isBST) // 右子树为二叉搜索子树
                && (leftInfo == null ? true : leftInfo.max < root.value) // 左子树最大值 < 当前结点值
                && (rightInfo == null ? true : rightInfo.min > root.value) // 右子树的最小值 > 当前结点值
        ) {
            info.maxBSTSubtreeSize = (leftInfo == null ? 0 : leftInfo.maxBSTSubtreeSize)
                                        + (rightInfo == null ? 0 : rightInfo.maxBSTSubtreeSize)
                                        + 1;
            info.isBST = true;
        }
        // (4) 返回info对象
        return info;
    }
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/84580.html