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