998. Maximum Binary Tree II Medium

1/**
2 * [998] Maximum Binary Tree II
3 *
4 * A maximum tree is a tree where every node has a value greater than any other value in its subtree.
5 * You are given the root of a maximum binary tree and an integer val.
6 * Just as in the <a href="https://leetcode.com/problems/maximum-binary-tree/" target="_blank">previous problem</a>, the given tree was constructed from a list a (root = Construct(a)) recursively with the following Construct(a) routine:
7 * 
8 * 	If a is empty, return null.
9 * 	Otherwise, let a[i] be the largest element of a. Create a root node with the value a[i].
10 * 	The left child of root will be Construct([a[0], a[1], ..., a[i - 1]]).
11 * 	The right child of root will be Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]]).
12 * 	Return root.
13 * 
14 * Note that we were not given a directly, only a root node root = Construct(a).
15 * Suppose b is a copy of a with the value val appended to it. It is guaranteed that b has unique values.
16 * Return Construct(b).
17 *  
18 * Example 1:
19 * <img alt="" src="https://assets.leetcode.com/uploads/2021/08/09/maxtree1.JPG" style="width: 376px; height: 235px;" />
20 * Input: root = [4,1,3,null,null,2], val = 5
21 * Output: [5,4,null,1,3,null,null,2]
22 * Explanation: a = [1,4,2,3], b = [1,4,2,3,5]
23 * 
24 * Example 2:
25 * <img alt="" src="https://assets.leetcode.com/uploads/2021/08/09/maxtree21.JPG" style="width: 358px; height: 156px;" />
26 * Input: root = [5,2,4,null,1], val = 3
27 * Output: [5,2,4,null,1,null,3]
28 * Explanation: a = [2,1,5,4], b = [2,1,5,4,3]
29 * 
30 * Example 3:
31 * <img alt="" src="https://assets.leetcode.com/uploads/2021/08/09/maxtree3.JPG" style="width: 404px; height: 180px;" />
32 * Input: root = [5,2,3,null,1], val = 4
33 * Output: [5,2,4,null,1,3]
34 * Explanation: a = [2,1,5,3], b = [2,1,5,3,4]
35 * 
36 *  
37 * Constraints:
38 * 
39 * 	The number of nodes in the tree is in the range [1, 100].
40 * 	1 <= Node.val <= 100
41 * 	All the values of the tree are unique.
42 * 	1 <= val <= 100
43 * 
44 */
45pub struct Solution {}
46use crate::util::tree::{TreeNode, to_tree};
47
48// problem: https://leetcode.com/problems/maximum-binary-tree-ii/
49// discuss: https://leetcode.com/problems/maximum-binary-tree-ii/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53// Definition for a binary tree node.
54// #[derive(Debug, PartialEq, Eq)]
55// pub struct TreeNode {
56//   pub val: i32,
57//   pub left: Option<Rc<RefCell<TreeNode>>>,
58//   pub right: Option<Rc<RefCell<TreeNode>>>,
59// }
60// 
61// impl TreeNode {
62//   #[inline]
63//   pub fn new(val: i32) -> Self {
64//     TreeNode {
65//       val,
66//       left: None,
67//       right: None
68//     }
69//   }
70// }
71use std::rc::Rc;
72use std::cell::RefCell;
73impl Solution {
74    pub fn insert_into_max_tree(root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
75        Some(Rc::new(RefCell::new(TreeNode::new(0))))
76    }
77}
78
79// submission codes end
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84
85    #[test]
86    fn test_998() {
87    }
88}
89