二叉树中最大的二叉搜索子树的大小

时间：2022-10-09 22:06:58

作者：Grey

原文地址：

博客园：二叉树中最大的二叉搜索子树的大小

CSDN：二叉树中最大的二叉搜索子树的大小

题目描述

求一个二叉树中的最大二叉搜索子树的大小

题目链接见：牛客-找到二叉树中的最大搜索二叉子树

思路1

判断一棵树是否是二叉搜索树，就是要判断一棵树的中序遍历结果是否严格递增，即

// 判断以 head 为头的树是否为二叉搜索树，如果是，返回节点个数，如果不是，返回0
    public static int getBSTSize(TreeNode head) {
        if (head == null) {
            return 0;
        }
        ArrayList<TreeNode> arr = new ArrayList<>();
        in(head, arr);
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i).value <= arr.get(i - 1).value) {
                return 0;
            }
        }
        return arr.size();
    }

// 收集中序遍历结果
    public static void in(TreeNode head, ArrayList<TreeNode> arr) {
        if (head == null) {
            return;
        }
        in(head.left, arr);
        arr.add(head);
        in(head.right, arr);
    }

有了getBSTSize方法，主函数调用

    public static int maxSubBSTSize1(TreeNode head) {
        if (head == null) {
            return 0;
        }
        // 以 head 为头的树如果是二叉搜索树，直接返回
        int h = getBSTSize(head);
        if (h != 0) {
            // 以head为头的树就是二叉搜索树，直接返回其大小
            return h;
        }
        // 递归调用，获取左边的最大二叉搜索树的大小和右边最大二叉搜索树大小
        // 两者中较大那个，就是答案
        return Math.max(maxSubBSTSize1(head.left), maxSubBSTSize1(head.right));
    }

思路1的完整代码如下

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;

// https://www.nowcoder.com/questionTerminal/380d49d7f99242709ab4b91c36bf2acc
public class Main {

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

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

    public static int getBSTSize(TreeNode head) {
        if (head == null) {
            return 0;
        }
        ArrayList<TreeNode> arr = new ArrayList<>();
        in(head, arr);
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i).value <= arr.get(i - 1).value) {
                return 0;
            }
        }
        return arr.size();
    }

    public static void in(TreeNode head, ArrayList<TreeNode> arr) {
        if (head == null) {
            return;
        }
        in(head.left, arr);
        arr.add(head);
        in(head.right, arr);
    }

    public static int maxSubBSTSize1(TreeNode head) {
        if (head == null) {
            return 0;
        }
        int h = getBSTSize(head);
        if (h != 0) {
            return h;
        }
        return Math.max(maxSubBSTSize1(head.left), maxSubBSTSize1(head.right));
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashMap<Integer, TreeNode> map = new HashMap<>();
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        int rootVal = Integer.parseInt(params[1]);
        // 构建二叉树
        TreeNode root = new TreeNode(rootVal);
        map.put(rootVal, root);
        for (int i = 0; i < n; i++) {
            params = br.readLine().split(" ");
            int nodeVal = Integer.parseInt(params[0]);
            int leftVal = Integer.parseInt(params[1]);
            int rightVal = Integer.parseInt(params[2]);
            TreeNode node = map.get(nodeVal);
            if (leftVal != 0) {
                node.left = new TreeNode(leftVal);
                map.put(leftVal, node.left);
            }
            if (rightVal != 0) {
                node.right = new TreeNode(rightVal);
                map.put(rightVal, node.right);
            }
        }
        System.out.println(maxSubBSTSize1(root));
    }

}

但是这个方法时间复杂度太高O(N^2)。

思路2

使用二叉树的递归套路来解，

第一步，定义 Info

    public static class Info {
        public Info(int maxSubBSTSize, int max, int min, boolean isBST) {
            this.maxSubBSTSize = maxSubBSTSize;
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
        // 二叉树的最大二叉搜索子树大小
        private int maxSubBSTSize;
        // 二叉树的最大值是多少
        private int max;
        // 二叉树的最小值是多少
        private int min;
        // 二叉树是否是二叉搜索树
        private boolean isBST;
    }

第二步，定义递归函数

static Info p(TreeNode head);

第三步，分析可能性

如果null == head 直接返回 null;

如果null != head，则获取左树提供的信息Info left和右树提供的信息Info right

        Info left = p(head.left);
        Info right = p(head.right);

然后根据左树的 Info 和右树的 Info 整合出 head 为头的树的 Info 信息返回，核心代码和注释信息如下：

        // 到这里，说明 head != null，所以maxSize至少是1
        int maxSize = 1;
        // max 和 min 先预置为 head.value
        int max = head.value;
        int min = head.value;
        // isBST 先设置为 true
        boolean isBST = true;
        if (left != null) {
            // 左树信息不为空，左树的最大值要比 head 值小，且左树要是BST，以head为头的树在不考虑右树的情况下，就是 true
            // 否则为 false
            isBST = left.isBST && left.max < head.value;
            // 左树的 max 可能会推高 head为头的树的max值
            max = Math.max(left.max, max);
            // 左树的 min 可能会推低 head为头的树的min值
            min = Math.min(left.min, min);
            maxSize = Math.max(maxSize, left.maxSubBSTSize);
        }
        if (right != null) {
            // 与left != null 分支注释类似
            isBST = isBST && right.isBST && right.min > head.value;
            max = Math.max(right.max, max);
            min = Math.min(right.min, min);
            maxSize = Math.max(maxSize, right.maxSubBSTSize);
        }
        if (isBST) {
            maxSize = Math.max((left != null ? left.maxSubBSTSize : 0) + (right != null ? right.maxSubBSTSize : 0) + 1, maxSize);
        }

思路2完整代码如下

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
 
public class Main {

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

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

    public static int maxSubBSTSize2(TreeNode head) {
        if (head == null) {
            return 0;
        }
        return p(head).maxSubBSTSize;
    }

    public static Info p(TreeNode head) {
        if (head == null) {
            return null;
        }
        Info left = p(head.left);
        Info right = p(head.right);
        int maxSize = 1;
        int max = head.value;
        int min = head.value;
        boolean isBST = true;
        if (left != null) {
            isBST = left.isBST && left.max < head.value;
            max = Math.max(left.max, max);
            min = Math.min(left.min, min);
            maxSize = Math.max(maxSize, left.maxSubBSTSize);
        }
        if (right != null) {
            isBST = isBST && right.isBST && right.min > head.value;
            max = Math.max(right.max, max);
            min = Math.min(right.min, min);
            maxSize = Math.max(maxSize, right.maxSubBSTSize);
        }
        if (isBST) {
            maxSize = Math.max((left != null ? left.maxSubBSTSize : 0) + (right != null ? right.maxSubBSTSize : 0) + 1, maxSize);
        }
        return new Info(maxSize, max, min, isBST);
    }

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

        private int maxSubBSTSize;
        private int max;
        private int min;
        private boolean isBST;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashMap<Integer, TreeNode> map = new HashMap<>();
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        int rootVal = Integer.parseInt(params[1]);
        // 构建二叉树
        TreeNode root = new TreeNode(rootVal);
        map.put(rootVal, root);
        for (int i = 0; i < n; i++) {
            params = br.readLine().split(" ");
            int nodeVal = Integer.parseInt(params[0]);
            int leftVal = Integer.parseInt(params[1]);
            int rightVal = Integer.parseInt(params[2]);
            TreeNode node = map.get(nodeVal);
            if (leftVal != 0) {
                node.left = new TreeNode(leftVal);
                map.put(leftVal, node.left);
            }
            if (rightVal != 0) {
                node.right = new TreeNode(rightVal);
                map.put(rightVal, node.right);
            }
        }
        // System.out.println(maxSubBSTSize1(root));
        System.out.println(maxSubBSTSize2(root));
    }

}

时间复杂度O(N)。

更多

算法和数据结构笔记

标签：

相关文章