資訊專欄INFORMATION COLUMN
摘要：復(fù)雜度思路考慮對(duì)于每一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，能組成的的。那么并且所以我們需要兩個(gè)返回值，一個(gè)是這個(gè)是不是，另一個(gè)是當(dāng)前的能組成的最大的值。代碼這個(gè)能構(gòu)成一個(gè)這個(gè)不能構(gòu)成一個(gè)
LeetCode[333] Largest BST Subtree
RecursionGiven 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. Here"s an
example:10 / 5 15 / 1 8 7The Largest BST Subtree in this case is the highlighted one. The return value is the subtree"s size,
which is 3.
復(fù)雜度
O(N), O(lgN)
思路
考慮對(duì)于每一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，能組成的largest binary tree的size。
if(isBinary(node.left) && isBinary(node.right)) {
if(node.val > node.left.val && node.val < node.right.val) {
//
那么node is binary
并且node.cnt = node.left.cnt + node.right.cnt;
}
}
else {
return node is not binary && Math.max(node.left.cnt, node.right.cnt);
}
所以我們需要兩個(gè)返回值，一個(gè)是這個(gè)node是不是binary tree，另一個(gè)是當(dāng)前的node能組成的最大size的值。
可以考慮定義一個(gè)新node來(lái)返回這兩個(gè)結(jié)果，或者通過(guò)返回一個(gè)數(shù)組，數(shù)組里面包含著兩個(gè)值來(lái)返回這兩個(gè)結(jié)果。
代碼
int num = 0;
public int largestBSTSubtree(TreeNode root) {
helper(root);
return num;
}
// in[] = {isBST, size, max, min};
public int[] helper(TreeNode root) {
if(root == null) return new int[]{1, 0, Integer.MIN_VALUE, Integer.MAX_VALUE};
int[] left = helper(root.left);
int[] right = helper(root.right);
int res = new int[4];
res[2] = Math.max(root.val, right[2]);
res[3] = Math.min(root.val, left[3]);
// 這個(gè)node能構(gòu)成一個(gè)Binary tree
if(left[0] == 1 && right[0] == 1 && root.val > left[2] && root.val < right[3]) {
res[0] = 1;
res[1] = left[1] + right[1] + 1;
num = Math.max(num, res[1]);
return res;
}
// 這個(gè)node不能構(gòu)成一個(gè)binary tree
res[0] = 0;
res[1] = Math.max(left[1], right[1]);
return res;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/65254.html
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 descen...
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...
閱讀 1684·2021-08-30 09:45
閱讀 1751·2019-08-30 15:54
閱讀 1169·2019-08-30 14:02
閱讀 1925·2019-08-29 16:21
閱讀 1609·2019-08-29 13:47
閱讀 3193·2019-08-29 12:27
閱讀 698·2019-08-29 11:01
閱讀 2659·2019-08-26 14:04
