Steven's Blog

Appearance

On this page

每天一道Rust-LeetCode(2019-08-15) ​

坚持每天一道题,刷题学习Rust.

题目描述 ​

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6
将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路 ​

相当于前序遍历,先把自身节点挂在链表上 然后取出left,right 再分别递归处理left,right

解题过程 ​

rust
use crate::share::TreeNode;
use std::cell::RefCell;
use std::rc::Rc;
struct Solution {}
impl Solution {
    pub fn flatten(root: &mut Option<Rc<RefCell<TreeNode>>>) {
        let mut pre = Some(Rc::new(RefCell::new(TreeNode::new(0))));
        Solution::flattern_internal(pre.unwrap(), root.clone());
    }
    fn flattern_internal(
        mut root: Rc<RefCell<TreeNode>>,
        mut cur: Option<Rc<RefCell<TreeNode>>>,
    ) -> Rc<RefCell<TreeNode>> {
        //        println!("root={:?},cur={:?}", root, cur);
        if let Some(r) = cur {
            root.borrow_mut().right = Some(r.clone());
            let root = root.borrow().right.clone().unwrap();
            let mut left = r.borrow_mut().left.take();
            let mut right = r.borrow_mut().right.take();
            //            println!("root={:?}", root);
            let root = Solution::flattern_internal(root, left);
            //            println!("rootleft={:?}", root);
            let root = Solution::flattern_internal(root, right);
            //            println!("root right={:?}", root);
            return root;
        }
        root
    }
}
#[cfg(test)]
mod tests {
    use crate::l114_flattern_binary_tree_to_linked_list::Solution;
    use crate::share::build_tree;
    use crate::share::NULL;

    #[test]
    fn test_flattern() {
        let mut t = build_tree(&vec![1, 2, 5, 3, 4, NULL, 6]);
        println!("before t={:?}", t);
        Solution::flatten(&mut t);
        println!("t={:?}", t);
    }
}

一点感悟 ​

使用rust确实能让思路更清晰,编译通过,结果就对了

其他 ​

欢迎关注我的github,本项目文章所有代码都可以找到.