1373. Maximum Sum BST in Binary Tree Hard

1/**
2 * [1373] Maximum Sum BST in Binary Tree
3 *
4 * Given a binary tree root, return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree (BST).
5 * Assume a BST is defined as follows:
6 * 
7 * 	The left subtree of a node contains only nodes with keys less than the node's key.
8 * 	The right subtree of a node contains only nodes with keys greater than the node's key.
9 * 	Both the left and right subtrees must also be binary search trees.
10 * 
11 *  
12 * Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2020/01/30/sample_1_1709.png" style="width: 320px; height: 250px;" />
14 * 
15 * Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
16 * Output: 20
17 * Explanation: Maximum sum in a valid Binary search tree is obtained in root node with key equal to 3.
18 * 
19 * Example 2:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2020/01/30/sample_2_1709.png" style="width: 134px; height: 180px;" />
21 * 
22 * Input: root = [4,3,null,1,2]
23 * Output: 2
24 * Explanation: Maximum sum in a valid Binary search tree is obtained in a single root node with key equal to 2.
25 * 
26 * Example 3:
27 * 
28 * Input: root = [-4,-2,-5]
29 * Output: 0
30 * Explanation: All values are negatives. Return an empty BST.
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	The number of nodes in the tree is in the range [1, 4 * 10^4].
36 * 	-4 * 10^4 <= Node.val <= 4 * 10^4
37 * 
38 */
39pub struct Solution {}
40use crate::util::tree::{TreeNode, to_tree};
41
42// problem: https://leetcode.com/problems/maximum-sum-bst-in-binary-tree/
43// discuss: https://leetcode.com/problems/maximum-sum-bst-in-binary-tree/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47// Definition for a binary tree node.
48// #[derive(Debug, PartialEq, Eq)]
49// pub struct TreeNode {
50//   pub val: i32,
51//   pub left: Option<Rc<RefCell<TreeNode>>>,
52//   pub right: Option<Rc<RefCell<TreeNode>>>,
53// }
54// 
55// impl TreeNode {
56//   #[inline]
57//   pub fn new(val: i32) -> Self {
58//     TreeNode {
59//       val,
60//       left: None,
61//       right: None
62//     }
63//   }
64// }
65use std::rc::Rc;
66use std::cell::RefCell;
67impl Solution {
68    pub fn max_sum_bst(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
69        0
70    }
71}
72
73// submission codes end
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test_1373() {
81    }
82}
83