二叉树中最大的二叉搜索子树的大小
二叉树中最大的二叉搜索子树的大小
作者：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;
// //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)。
