226. Invert Binary Tree
Invert a binary tree.
Example:
Input:
4 / \ 2 7 / \ / \ 1 3 6 9
Output:
4 / \ 7 2 / \ / \ 9 6 3 1
Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.
Rust Solution
struct Solution;
use rustgym_util::*;
impl Solution {
fn invert_tree(root: TreeLink) -> TreeLink {
if let Some(node) = &root {
let mut node = node.borrow_mut();
let left = node.left.take();
let right = node.right.take();
node.right = Self::invert_tree(left);
node.left = Self::invert_tree(right);
}
root
}
}
#[test]
fn test() {
let input = tree!(
4,
tree!(2, tree!(1), tree!(3)),
tree!(7, tree!(6), tree!(9))
);
let output = tree!(
4,
tree!(7, tree!(9), tree!(6)),
tree!(2, tree!(3), tree!(1))
);
assert_eq!(Solution::invert_tree(input), output);
}
Having problems with this solution? Click here to submit an issue on github.