二叉树中最大的二叉搜索子树的大小
作者：Grey
原文地址：
题目描述
求一个二叉树中的最大二叉搜索子树的大小
题目链接见：牛客-找到二叉树中的最大搜索二叉子树
思路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)。
