Given the root
of a binary tree, turn the tree upside down and return the new root.
You can turn a binary tree upside down with the following steps:
The mentioned steps are done level by level, it is guaranteed that every node in the given tree has either 0 or 2 children.
Example 1:
Input: root = [1,2,3,4,5] Output: [4,5,2,null,null,3,1]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [1] Output: [1]
Constraints:
[0, 10]
.1 <= Node.val <= 10
Every node has either 0 or 2 children.
struct Solution;
use rustgym_util::*;
trait Preorder {
fn preorder(self, left: TreeLink, right: TreeLink) -> TreeLink;
}
impl Preorder for TreeLink {
fn preorder(self, left: TreeLink, right: TreeLink) -> TreeLink {
if let Some(node) = self {
let left_tree = node.borrow_mut().left.take();
let right_leaf = node.borrow_mut().right.take();
node.borrow_mut().left = left;
node.borrow_mut().right = right;
left_tree.preorder(right_leaf, Some(node))
} else {
right
}
}
}
impl Solution {
fn upside_down_binary_tree(root: TreeLink) -> TreeLink {
root.preorder(None, None)
}
}
#[test]
fn test() {
let root = tree!(1, tree!(2, tree!(4), tree!(5)), tree!(3));
let res = tree!(4, tree!(5), tree!(2, tree!(3), tree!(1)));
assert_eq!(Solution::upside_down_binary_tree(root), res);
}