05 August 2008
给定二叉树的根，找到最大的子树，它也是二叉搜索树（BST），其中最大的意味着子树的节点数最多。
二叉搜索树 (BST) 是一棵树，其中所有节点都遵循以下属性：
左子树的值小于其父（根）节点的值。
右子树的值大于其父（根）节点的值。
注意：子树必须包括它的所有后代。
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
class Node {
int min; // minimum value of current subtree
int max; // maximum value of current subtree
boolean isBST;
int count; // count of tree
public Node(int min, int max, boolean isBST, int count) {
this.min = min;
this.max = max;
this.isBST = isBST;
this.count = count;
}
}
public int largestBSTSubtree(TreeNode root) {
Node curr = getSubtree(root);
return curr.count;
}
public Node getSubtree(TreeNode node) {
if (node == null) {
return new Node(Integer.MAX_VALUE, Integer.MIN_VALUE, true, 0);
}
Node left = getSubtree(node.left);
Node right = getSubtree(node.right);
if (left.isBST && right.isBST && node.val > left.max && node.val < right.min) {
return new Node(Math.min(left.min, node.val),Math.max(right.max,node.val), true, left.count + right.count + 1);
}
return new Node(0, 0, false, Math.max(left.count , right.count)); // if not BST, we don;t need to keep min and max anymore
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
private int largestBSTSize = 0;
public int largestBSTSubtree(TreeNode root) {
dfs(root);
return largestBSTSize;
}
private int[] dfs(TreeNode root) {
if (root == null) return new int[]{0, Integer.MAX_VALUE, Integer.MIN_VALUE};
int[] leftInfo = dfs(root.left);
int[] rightInfo = dfs(root.right);
if (leftInfo[0] == 0 && root.left != null) return leftInfo;
if (rightInfo[0] == 0 && root.right != null) return rightInfo;
// rootInfo[0] saves the max size of BST rooted at the current node
// rootInfo[1] saves the min val of BST rooted at the current node
// rootInfo[2] saves the max val of BST rooted at the current node
int[] rootInfo = {0, root.val, root.val};
boolean isLeftSatisfied = root.val > leftInfo[2];
boolean isRightSatisfied = root.val < rightInfo[1];
if (isLeftSatisfied && isRightSatisfied) {
rootInfo[0] = leftInfo[0] + rightInfo[0] + 1;
rootInfo[1] = root.left == null ? root.val:leftInfo[1];
rootInfo[2] = root.right == null ? root.val:rightInfo[2];
largestBSTSize = Math.max(largestBSTSize, rootInfo[0]);
}
return rootInfo;
}
}