{"content":{"title":"Rust每日一题(15)--数据结构--二叉树的前序遍历","body":"## 问题描述\r\n给你二叉树的根节点root,返回它节点值的`前序`遍历。\r\n[leetcode](https://leetcode-cn.com/problems/binary-tree-preorder-traversal)\r\n\r\n## 解题思路\r\n思路比较简单，可以采用递归或队列的方式来解决\r\n主要是熟悉Rust以下几部分内容:\r\n- Option可以采用`Some`或者`.map`来进行模式匹配，对里面的数据解包，有几层Option就采用几层`Some`或`.map`\r\n- 对于Box<T>和Rc<T>而言其所有的数据T，由于存在自动解引用，可以直接采用普通引用的所有操作(调用方法或获取属性)，因此可以认为这两者对于T是透明的；但是对于Rc<RefCell<T>>>则不一样了，RefCell需要先通过`borrow`或`borrow_mut`来获取对内部数据T的借用;\r\n- &mut T类型的数据没有实现Copy Trait(否则就会有两个可变借用),因此对root赋值时`node.borrow().right.clone()`采用`clone()`的方式否则会转移所right的所有权\r\n\r\n## Rust代码实现\r\n\r\n```\r\n// Definition for a binary tree node.\r\n#[derive(Debug, PartialEq, Eq)]\r\npub struct TreeNode {\r\n  pub val: i32,\r\n  pub left: Option<Rc<RefCell<TreeNode>>>,\r\n  pub right: Option<Rc<RefCell<TreeNode>>>,\r\n}\r\n\r\nimpl TreeNode {\r\n  #[inline]\r\n  pub fn new(val: i32) -> Self {\r\n    TreeNode {\r\n      val,\r\n      left: None,\r\n      right: None\r\n    }\r\n  }\r\n}\r\n\r\nuse std::rc::Rc;\r\nuse std::cell::RefCell;\r\nstruct Solution{}\r\nimpl Solution {\r\n    pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {\r\n      let mut res = vec![];\r\n      // Solution::recursive(root, &mut res);\r\n      Solution::iterate(root, &mut res);\r\n      res\r\n    }\r\n\r\n    fn recursive(root: Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>){\r\n      if let Some(x  ) = root {\r\n        res.push(x.borrow().val);\r\n        //访问左子节点\r\n        Solution::recursive(x.borrow().left.clone(), res);\r\n        Solution::recursive(x.borrow().right.clone(), res);\r\n      }\r\n    }\r\n\r\n    fn iterate(mut root: Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>) {\r\n      let mut heap = vec![];\r\n      //1.遍历完节点并入栈\r\n      while root.is_some() || !heap.is_empty() {\r\n        //访问所有左子树\r\n        while let Some(node) = root {\r\n          //invirant root shrink\r\n          res.push(node.borrow().val);\r\n          heap.push(node.clone());\r\n          root = node.borrow().left.clone();\r\n        }\r\n        root = heap.pop();\r\n        if let Some(node) = root {\r\n          root = node.borrow().right.clone();\r\n        }\r\n      }\r\n    }\r\n}\r\n\r\nfn main(){\r\n  let mut root = TreeNode::new(2);\r\n  let left_1 = None;\r\n  let left_2= TreeNode::new(1);\r\n  let mut right = TreeNode::new(3);\r\n  right.right = None;\r\n  right.left = Some(Rc::new(RefCell::new(left_2)));\r\n  root.left = left_1;\r\n  root.right = Some(Rc::new(RefCell::new(right)));\r\n\r\n  let res = Solution::preorder_traversal(Some(Rc::new(RefCell::new(root))));\r\n  println!(\"{:?}\", res);\r\n}\r\n```"},"author":{"user":"https://learnblockchain.cn/people/720","address":null},"history":null,"timestamp":1674033930,"version":1}