654. Maximum Binary Tree Medium

1/**
2 * [654] Maximum Binary Tree
3 *
4 * You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:
5 * <ol>
6 * 	Create a root node whose value is the maximum value in nums.
7 * 	Recursively build the left subtree on the subarray prefix to the left of the maximum value.
8 * 	Recursively build the right subtree on the subarray suffix to the right of the maximum value.
9 * </ol>
10 * Return the maximum binary tree built from nums.
11 *  
12 * Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2020/12/24/tree1.jpg" style="width: 302px; height: 421px;" />
14 * Input: nums = [3,2,1,6,0,5]
15 * Output: [6,3,5,null,2,0,null,null,1]
16 * Explanation: The recursive calls are as follow:
17 * - The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
18 *     - The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
19 *         - Empty array, so no child.
20 *         - The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
21 *             - Empty array, so no child.
22 *             - Only one element, so child is a node with value 1.
23 *     - The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
24 *         - Only one element, so child is a node with value 0.
25 *         - Empty array, so no child.
26 * 
27 * Example 2:
28 * <img alt="" src="https://assets.leetcode.com/uploads/2020/12/24/tree2.jpg" style="width: 182px; height: 301px;" />
29 * Input: nums = [3,2,1]
30 * Output: [3,null,2,null,1]
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	1 <= nums.length <= 1000
36 * 	0 <= nums[i] <= 1000
37 * 	All integers in nums are unique.
38 * 
39 */
40pub struct Solution {}
41use crate::util::tree::{TreeNode, to_tree};
42
43// problem: https://leetcode.com/problems/maximum-binary-tree/
44// discuss: https://leetcode.com/problems/maximum-binary-tree/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48// Definition for a binary tree node.
49// #[derive(Debug, PartialEq, Eq)]
50// pub struct TreeNode {
51//   pub val: i32,
52//   pub left: Option<Rc<RefCell<TreeNode>>>,
53//   pub right: Option<Rc<RefCell<TreeNode>>>,
54// }
55// 
56// impl TreeNode {
57//   #[inline]
58//   pub fn new(val: i32) -> Self {
59//     TreeNode {
60//       val,
61//       left: None,
62//       right: None
63//     }
64//   }
65// }
66use std::rc::Rc;
67use std::cell::RefCell;
68impl Solution {
69    pub fn construct_maximum_binary_tree(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
70        Some(Rc::new(RefCell::new(TreeNode::new(0))))
71    }
72}
73
74// submission codes end
75
76#[cfg(test)]
77mod tests {
78    use super::*;
79
80    #[test]
81    fn test_654() {
82    }
83}
84