2415. Reverse Odd Levels of Binary Tree Medium

1/**
2 * [2415] Reverse Odd Levels of Binary Tree
3 *
4 * Given the root of a perfect binary tree, reverse the node values at each odd level of the tree.
5 * 
6 * 	For example, suppose the node values at level 3 are [2,1,3,4,7,11,29,18], then it should become [18,29,11,7,4,3,1,2].
7 * 
8 * Return the root of the reversed tree.
9 * A binary tree is perfect if all parent nodes have two children and all leaves are on the same level.
10 * The level of a node is the number of edges along the path between it and the root node.
11 *  
12 * Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2022/07/28/first_case1.png" style="width: 626px; height: 191px;" />
14 * Input: root = [2,3,5,8,13,21,34]
15 * Output: [2,5,3,8,13,21,34]
16 * Explanation: 
17 * The tree has only one odd level.
18 * The nodes at level 1 are 3, 5 respectively, which are reversed and become 5, 3.
19 * 
20 * Example 2:
21 * <img alt="" src="https://assets.leetcode.com/uploads/2022/07/28/second_case3.png" style="width: 591px; height: 111px;" />
22 * Input: root = [7,13,11]
23 * Output: [7,11,13]
24 * Explanation: 
25 * The nodes at level 1 are 13, 11, which are reversed and become 11, 13.
26 * 
27 * Example 3:
28 * 
29 * Input: root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
30 * Output: [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
31 * Explanation: 
32 * The odd levels have non-zero values.
33 * The nodes at level 1 were 1, 2, and are 2, 1 after the reversal.
34 * The nodes at level 3 were 1, 1, 1, 1, 2, 2, 2, 2, and are 2, 2, 2, 2, 1, 1, 1, 1 after the reversal.
35 * 
36 *  
37 * Constraints:
38 * 
39 * 	The number of nodes in the tree is in the range [1, 2^14].
40 * 	0 <= Node.val <= 10^5
41 * 	root is a perfect binary tree.
42 * 
43 */
44pub struct Solution {}
45use crate::util::tree::{TreeNode, to_tree};
46
47// problem: https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/
48// discuss: https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52// Definition for a binary tree node.
53// #[derive(Debug, PartialEq, Eq)]
54// pub struct TreeNode {
55//   pub val: i32,
56//   pub left: Option<Rc<RefCell<TreeNode>>>,
57//   pub right: Option<Rc<RefCell<TreeNode>>>,
58// }
59// 
60// impl TreeNode {
61//   #[inline]
62//   pub fn new(val: i32) -> Self {
63//     TreeNode {
64//       val,
65//       left: None,
66//       right: None
67//     }
68//   }
69// }
70use std::rc::Rc;
71use std::cell::RefCell;
72impl Solution {
73    pub fn reverse_odd_levels(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
74        Some(Rc::new(RefCell::new(TreeNode::new(0))))
75    }
76}
77
78// submission codes end
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83
84    #[test]
85    fn test_2415() {
86    }
87}
88