623. Add One Row to Tree Medium

1/**
2 * [623] Add One Row to Tree
3 *
4 * Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth depth.
5 * Note that the root node is at depth 1.
6 * The adding rule is:
7 * 
8 * 	Given the integer depth, for each not null tree node cur at the depth depth - 1, create two tree nodes with value val as cur's left subtree root and right subtree root.
9 * 	cur's original left subtree should be the left subtree of the new left subtree root.
10 * 	cur's original right subtree should be the right subtree of the new right subtree root.
11 * 	If depth == 1 that means there is no depth depth - 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root's left subtree.
12 * 
13 *  
14 * Example 1:
15 * <img alt="" src="https://assets.leetcode.com/uploads/2021/03/15/addrow-tree.jpg" style="width: 500px; height: 231px;" />
16 * Input: root = [4,2,6,3,1,5], val = 1, depth = 2
17 * Output: [4,1,1,2,null,null,6,3,1,5]
18 * 
19 * Example 2:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2021/03/11/add2-tree.jpg" style="width: 500px; height: 277px;" />
21 * Input: root = [4,2,null,3,1], val = 1, depth = 3
22 * Output: [4,2,null,1,1,3,null,null,1]
23 * 
24 *  
25 * Constraints:
26 * 
27 * 	The number of nodes in the tree is in the range [1, 10^4].
28 * 	The depth of the tree is in the range [1, 10^4].
29 * 	-100 <= Node.val <= 100
30 * 	-10^5 <= val <= 10^5
31 * 	1 <= depth <= the depth of tree + 1
32 * 
33 */
34pub struct Solution {}
35use crate::util::tree::{TreeNode, to_tree};
36
37// problem: https://leetcode.com/problems/add-one-row-to-tree/
38// discuss: https://leetcode.com/problems/add-one-row-to-tree/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42// Definition for a binary tree node.
43// #[derive(Debug, PartialEq, Eq)]
44// pub struct TreeNode {
45//   pub val: i32,
46//   pub left: Option<Rc<RefCell<TreeNode>>>,
47//   pub right: Option<Rc<RefCell<TreeNode>>>,
48// }
49// 
50// impl TreeNode {
51//   #[inline]
52//   pub fn new(val: i32) -> Self {
53//     TreeNode {
54//       val,
55//       left: None,
56//       right: None
57//     }
58//   }
59// }
60use std::rc::Rc;
61use std::cell::RefCell;
62impl Solution {
63    pub fn add_one_row(root: Option<Rc<RefCell<TreeNode>>>, val: i32, depth: i32) -> Option<Rc<RefCell<TreeNode>>> {
64        Some(Rc::new(RefCell::new(TreeNode::new(0))))
65    }
66}
67
68// submission codes end
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_623() {
76    }
77}
78