leetcode/
invert_tree.rs

1//! # 226. 翻转二叉树
2//!
3//! 难度 简单
4//!
5//! 翻转一棵二叉树。
6//!
7//! ## 示例：
8//!
9//! 输入：
10//! ```text
11//!      4
12//!    /   \
13//!   2     7
14//!  / \   / \
15//! 1   3 6   9
16//! ```
17//!
18//! 输出：
19//! ```text
20//!      4
21//!    /   \
22//!   7     2
23//!  / \   / \
24//! 9   6 3   1
25//! ```
26//!
27//! ## 备注:
28//! 这个问题是受到 [Max Howell](https://twitter.com/mxcl) 的 [原问题](https://twitter.com/mxcl/status/608682016205344768) 启发的 ：
29//!
30//! > 谷歌：我们 90％ 的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
31
32use std::rc::Rc;
33use std::cell::RefCell;
34
35use crate::TreeNode;
36
37pub struct Solution;
38
39impl Solution {
40    pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
41        root.as_ref().map(|r| Solution::invert_node(&mut r.borrow_mut()));
42        root
43    }
44
45    fn invert_node(n: &mut TreeNode) {
46        if let Some(node) = n.left.as_ref() {
47            Solution::invert_node(&mut node.borrow_mut());
48        }
49        if let Some(node) = n.right.as_ref() {
50            Solution::invert_node(&mut node.borrow_mut());
51        }
52        std::mem::swap(&mut n.left, &mut n.right)
53    }
54}
55
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60    use crate::tree;
61
62    #[test]
63    fn test() {
64        let t = |v| Solution::invert_tree(v);
65        assert_eq!(tree![4,7,2,9,6], t(tree![4,2,7,null,null,6,9]));
66        assert_eq!(tree![4,7,2,9,6,3,1], t(tree![4,2,7,1,3,6,9]));
67        assert_eq!(tree![4,7,2], t(tree![4,2,7]));
68        assert_eq!(tree![4,7], t(tree![4,null,7]));
69        assert_eq!(tree![4,null,2], t(tree![4,2]));
70        assert_eq!(tree![], t(tree![]));
71    }
72}
leetcode/invert_tree.rs

leetcode/
invert_tree.rs
