662. Maximum Width of Binary Tree Medium

1/**
2 * [662] Maximum Width of Binary Tree
3 *
4 * Given the root of a binary tree, return the maximum width of the given tree.
5 * The maximum width of a tree is the maximum width among all levels.
6 * The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.
7 * It is guaranteed that the answer will in the range of a 32-bit signed integer.
8 *  
9 * Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2021/05/03/width1-tree.jpg" style="width: 359px; height: 302px;" />
11 * Input: root = [1,3,2,5,3,null,9]
12 * Output: 4
13 * Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).
14 * 
15 * Example 2:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/14/maximum-width-of-binary-tree-v3.jpg" style="width: 442px; height: 422px;" />
17 * Input: root = [1,3,2,5,null,null,9,6,null,7]
18 * Output: 7
19 * Explanation: The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).
20 * 
21 * Example 3:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2021/05/03/width3-tree.jpg" style="width: 289px; height: 299px;" />
23 * Input: root = [1,3,2,5]
24 * Output: 2
25 * Explanation: The maximum width exists in the second level with length 2 (3,2).
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	The number of nodes in the tree is in the range [1, 3000].
31 * 	-100 <= Node.val <= 100
32 * 
33 */
34pub struct Solution {}
35use crate::util::tree::{TreeNode, to_tree};
36
37// problem: https://leetcode.com/problems/maximum-width-of-binary-tree/
38// discuss: https://leetcode.com/problems/maximum-width-of-binary-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 width_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
64        0
65    }
66}
67
68// submission codes end
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_662() {
76    }
77}
78