資訊專欄INFORMATION COLUMN
Problem
Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.
Note:
A subtree must include all of its descendants.
Example:
Input: [10,5,15,1,8,null,7]
10
/
5 15
/
1 8 7
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one.
The return value is the subtree"s size, which is 3.
Follow up:
Can you figure out ways to solve it with O(n) time complexity?
First try:
class Solution {
public int largestBSTSubtree(TreeNode root) {
if (root == null) return 0;
if (isBST(root)) return largestBSTSubtree(root.left)+largestBSTSubtree(root.right)+1;
return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
}
private boolean isBST(TreeNode root) {
if (root == null) return true;
if (root.left != null && findMax(root.left) >= root.val) return false;
if (root.right != null && findMin(root.right) <= root.val) return false;
if (isBST(root.left) && isBST(root.right)) return true;
return false;
}
private int findMax(TreeNode root) {
while (root.right != null) root = root.right;
return root.val;
}
private int findMin(TreeNode root) {
while (root.left != null) root = root.left;
return root.val;
}
}
Optimized:
class Solution {
public int largestBSTSubtree(TreeNode root) {
if (root == null) return 0;
if (isBST(root, null, null)) return largestBSTSubtree(root.left)+largestBSTSubtree(root.right)+1;
return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
}
private boolean isBST(TreeNode root, Integer min, Integer max) {
if (root == null) return true;
if (min != null && min >= root.val) return false;
if (max != null && max <= root.val) return false;
if (isBST(root.left, min, root.val) && isBST(root.right, root.val, max)) return true;
return false;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72038.html
摘要：復(fù)雜度思路考慮對于每一個(gè)節(jié)點(diǎn)來說，能組成的的。那么并且所以我們需要兩個(gè)返回值，一個(gè)是這個(gè)是不是，另一個(gè)是當(dāng)前的能組成的最大的值。代碼這個(gè)能構(gòu)成一個(gè)這個(gè)不能構(gòu)成一個(gè) LeetCode[333] Largest BST Subtree Given a binary tree, find the largest subtree which is a Binary SearchTree (B...
Largest BST Subtree Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it. Note: A subtree must include all ...
10 / 5 15 / 1 8 7 return 3 public class Solution { public int largestBSTSubtree(TreeNode root) { if(root == null) return 0; int[] res = recursive(root); ...
Problem Given a Binary Search Tree (BST) with root node root, and a target value V, split the tree into two subtrees where one subtree has nodes that are all smaller or equal to the target value, whil...
Problem Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST. Assume a BST is defined as follows: The left subtree of a node c...
閱讀 1423·2021-09-23 11:21
閱讀 3119·2019-08-30 14:14
閱讀 3205·2019-08-30 13:56
閱讀 4156·2019-08-30 11:20
閱讀 1962·2019-08-29 17:23
閱讀 2778·2019-08-29 16:14
閱讀 1708·2019-08-28 18:18
閱讀 1499·2019-08-26 12:14
