226. 翻转二叉树

题目

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

题型归类: 二叉树

因为写代码需要进行本地测试，所以先构建一个本地环境，可以很方便的生成TreeNode, 把一个Vec，生成一颗树。

#[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,
        }
    }
}

impl TreeNode {

    pub fn add_left(&mut self, val: i32) {
        let node = TreeNode::new(val);
        self.left = Some(Rc::new(RefCell::new(node)));
    }

    pub fn add_left_node(&mut self, node: TreeNode) {
        self.left = Some(Rc::new(RefCell::new(node)));
    }
    pub fn add_right(&mut self, val: i32) {
        let node = TreeNode::new(val);
        self.right = Some(Rc::new(RefCell::new(node)));
    }

    pub fn add_right_node(&mut self, node: TreeNode) {
        self.right = Some(Rc::new(RefCell::new(node)));
    }
}

思路一

从树的最顶端开始，一层一层往下，因为没法获取树的深度，所以只能使用递归来做了。

// 代码实现
impl Solution {
    pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut tree_node = root;

        match &tree_node {
            Some(ref n) => {
                let l = (*n.borrow()).left.clone();
                let r = (*n.borrow()).right.clone();
                (*n.borrow_mut()).left = Solution::invert_tree(r);
                (*n.borrow_mut()).right = Solution::invert_tree(l);
            }
            None => ()
        };
        tree_node
    }
}


#[cfg(test)]
mod test {
    use crate::{Solution, TreeNode};
    use std::rc::Rc;
    use std::cell::RefCell;

    #[test]
    pub fn invert_tree_test() {
        let mut node2 = TreeNode::new(2);
        node2.add_left(1);
        node2.add_right(3);

        let node = Rc::new(RefCell::new(node2));

        let l = Some(Rc::new(RefCell::new( TreeNode { val: 1, left: None, right: None } )));
        let r = Some(Rc::new(RefCell::new( TreeNode { val: 3, left: None, right: None } )));
        let n = Some(Rc::new(RefCell::new( TreeNode { val: 2, left: l.clone(), right: r.clone() } )));
        let n2 = Some(Rc::new(RefCell::new( TreeNode { val: 2, left: r.clone(), right: l.clone() } )));

        assert_eq!(n, Some(node.clone()));

        let n = Solution::invert_tree(n);
        assert_eq!(n2, n);

        let n = Solution::invert_tree(n);

        assert_ne!(n2, n);

    }
}

leetcode执行结果

执行用时 : 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
内存消耗 : 2 MB , 在所有 Rust 提交中击败了 100.00% 的用户

遇到难点

1. 如何用动态的tuple参数传入生成树？比如传入参数(1, (2, 4, 5), (6,7,8)) 或者 (1,2,3) 就生成对应的树，但是tuple是不可变的，应该怎样用一个序列简单的表示一颗树，然后调用函数来生成呢？Json？
2. 写测试用例时，直接用代码来表示结果数据，有大量的格式，不方便阅读和维护，比较麻烦，不知道有啥好办法来写结果。比如：

   Some(
       RefCell {
           value: TreeNode {
               val: 4,
               left: None,
               right: Some(
                   RefCell {
                       value: TreeNode {
                           val: 7,
                           left: Some(
                               RefCell {
                                   value: TreeNode {
                                       val: 9,
                                       left: None,
                                       right: None,
                                   },
                               },
                           ),
                           right: Some(
                               RefCell {
                                   value: TreeNode {
                                       val: 6,
                                       left: None,
                                       right: None,
                                   },
                               },
                           ),
                       },
                   },
               ),
           },
       },
   )
   
   

leetcode相似题型

无

2019-09-07 11:04