RUST GYM v0.2.4

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.