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

题目描述​​#​​

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

思路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)​​。