Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2415.html
2415. Reverse Odd Levels of Binary Tree
- Difficulty: Medium.
- Related Topics: .
- Similar Questions: Invert Binary Tree.
Problem
Given the root
of a perfect binary tree, reverse the node values at each odd level of the tree.
- 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]
.
Return the root of the reversed tree.
A binary tree is perfect if all parent nodes have two children and all leaves are on the same level.
The level of a node is the number of edges along the path between it and the root node.
Example 1:
Input: root = [2,3,5,8,13,21,34]
Output: [2,5,3,8,13,21,34]
Explanation:
The tree has only one odd level.
The nodes at level 1 are 3, 5 respectively, which are reversed and become 5, 3.
Example 2:
Input: root = [7,13,11]
Output: [7,11,13]
Explanation:
The nodes at level 1 are 13, 11, which are reversed and become 11, 13.
Example 3:
Input: root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
Output: [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
Explanation:
The odd levels have non-zero values.
The nodes at level 1 were 1, 2, and are 2, 1 after the reversal.
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.
Constraints:
-
The number of nodes in the tree is in the range
[1, 214]
. -
0 <= Node.val <= 105
-
root
is a perfect binary tree.
Solution (Java, C++, Python)
-
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode reverseOddLevels(TreeNode root) { if(root == null) return root; Queue<TreeNode> queue = new LinkedList<>(); int level = 0; queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); level++; TreeNode[] arr = new TreeNode[size]; for (int i = 0; i < size; i++) { TreeNode cur = queue.poll(); arr[i] = cur; if(cur.left != null){ queue.add(cur.left); queue.add(cur.right); } } if (level % 2 == 0) { int left = 0; int right = size - 1; while (left < right) { int leftVal = arr[left].val; arr[left].val = arr[right].val; arr[right].val = leftVal; left++; right--; } } } return root; } }
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]: q = deque([root]) i = 0 while q: t = [] for _ in range(len(q)): node = q.popleft() if i & 1: t.append(node) if node.left: q.append(node.left) if node.right: q.append(node.right) if t: j, k = 0, len(t) - 1 while j < k: t[j].val, t[k].val = t[k].val, t[j].val j, k = j + 1, k - 1 i += 1 return root ############ # 2415. Reverse Odd Levels of Binary Tree # https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/ # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]: res = [] dq = deque([root]) level = 0 while dq: n = len(dq) curr = [] for _ in range(n): node = dq.popleft() curr.append(node.val) for child in filter(None, (node.left, node.right)): dq.append(child) if level % 2 == 1: curr.reverse() res += curr level += 1 n = len(res) def go(i): root = None if i < n: root = TreeNode(res[i]) # insert left child root.left = go(2 * i + 1) # insert right child root.right = go(2 * i + 2) return root return go(0)
-
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* reverseOddLevels(TreeNode* root) { queue<TreeNode*> q{ {root} }; int i = 0; vector<TreeNode*> t; while (!q.empty()) { t.clear(); for (int n = q.size(); n; --n) { TreeNode* node = q.front(); q.pop(); if (i & 1) { t.push_back(node); } if (node->left) { q.push(node->left); } if (node->right) { q.push(node->right); } } if (t.size()) { int j = 0, k = t.size() - 1; for (; j < k; ++j, --k) { int v = t[j]->val; t[j]->val = t[k]->val; t[k]->val = v; } } ++i; } return root; } };
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func reverseOddLevels(root *TreeNode) *TreeNode { q := []*TreeNode{root} i := 0 for len(q) > 0 { t := []*TreeNode{} for n := len(q); n > 0; n-- { node := q[0] q = q[1:] if i%2 == 1 { t = append(t, node) } if node.Left != nil { q = append(q, node.Left) } if node.Right != nil { q = append(q, node.Right) } } if len(t) > 0 { j, k := 0, len(t)-1 for ; j < k; j, k = j+1, k-1 { v := t[j].Val t[j].Val = t[k].Val t[k].Val = v } } i++ } return root }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function reverseOddLevels(root: TreeNode | null): TreeNode | null { const queue = [root]; let d = 0; while (queue.length !== 0) { const n = queue.length; const t: TreeNode[] = []; for (let i = 0; i < n; i++) { const node = queue.shift(); if (d % 2 == 1) { t.push(node); } node.left && queue.push(node.left); node.right && queue.push(node.right); } const m = t.length; for (let i = 0; i < m >> 1; i++) { [t[i].val, t[m - 1 - i].val] = [t[m - 1 - i].val, t[i].val]; } d++; } return root; }
-
// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: Option<Rc<RefCell<TreeNode>>>, // pub right: Option<Rc<RefCell<TreeNode>>>, // } // // impl TreeNode { // #[inline] // pub fn new(val: i32) -> Self { // TreeNode { // val, // left: None, // right: None // } // } // } use std::rc::Rc; use std::cell::RefCell; use std::collections::VecDeque; impl Solution { fn create_tree(vals: &Vec<Vec<i32>>, i: usize, j: usize) -> Option<Rc<RefCell<TreeNode>>> { if i == vals.len() { return None; } Some(Rc::new(RefCell::new(TreeNode { val: vals[i][j], left: Self::create_tree(vals, i + 1, j * 2), right: Self::create_tree(vals, i + 1, j * 2 + 1), }))) } pub fn reverse_odd_levels( root: Option<Rc<RefCell<TreeNode>>>, ) -> Option<Rc<RefCell<TreeNode>>> { let mut queue = VecDeque::new(); queue.push_back(root); let mut d = 0; let mut vals = Vec::new(); while !queue.is_empty() { let mut val = Vec::new(); for _ in 0..queue.len() { let mut node = queue.pop_front().unwrap(); let mut node = node.as_mut().unwrap().borrow_mut(); val.push(node.val); if node.left.is_some() { queue.push_back(node.left.take()); } if node.right.is_some() { queue.push_back(node.right.take()); } } if d % 2 == 1 { val.reverse(); } vals.push(val); d += 1; } Self::create_tree(&vals, 0, 0) } }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).