Rust每日一题(15)--数据结构--二叉树的前序遍历

问题描述

给你二叉树的根节点root,返回它节点值的前序遍历。 leetcode

解题思路

思路比较简单，可以采用递归或队列的方式来解决 主要是熟悉Rust以下几部分内容:

• Option可以采用Some或者.map来进行模式匹配，对里面的数据解包，有几层Option就采用几层Some或.map
• 对于Box<T>和Rc<T>而言其所有的数据T，由于存在自动解引用，可以直接采用普通引用的所有操作(调用方法或获取属性)，因此可以认为这两者对于T是透明的；但是对于Rc<RefCell<T>>>则不一样了，RefCell需要先通过borrow或borrow_mut来获取对内部数据T的借用;
• &mut T类型的数据没有实现Copy Trait(否则就会有两个可变借用),因此对root赋值时node.borrow().right.clone()采用clone()的方式否则会转移所right的所有权

Rust代码实现

// Definition for a binary tree node.
#[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
    }
  }
}

use std::rc::Rc;
use std::cell::RefCell;
struct Solution{}
impl Solution {
    pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
      let mut res = vec![];
      // Solution::recursive(root, &mut res);
      Solution::iterate(root, &mut res);
      res
    }

    fn recursive(root: Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>){
      if let Some(x  ) = root {
        res.push(x.borrow().val);
        //访问左子节点
        Solution::recursive(x.borrow().left.clone(), res);
        Solution::recursive(x.borrow().right.clone(), res);
      }
    }

    fn iterate(mut root: Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>) {
      let mut heap = vec![];
      //1.遍历完节点并入栈
      while root.is_some() || !heap.is_empty() {
        //访问所有左子树
        while let Some(node) = root {
          //invirant root shrink
          res.push(node.borrow().val);
          heap.push(node.clone());
          root = node.borrow().left.clone();
        }
        root = heap.pop();
        if let Some(node) = root {
          root = node.borrow().right.clone();
        }
      }
    }
}

fn main(){
  let mut root = TreeNode::new(2);
  let left_1 = None;
  let left_2= TreeNode::new(1);
  let mut right = TreeNode::new(3);
  right.right = None;
  right.left = Some(Rc::new(RefCell::new(left_2)));
  root.left = left_1;
  root.right = Some(Rc::new(RefCell::new(right)));

  let res = Solution::preorder_traversal(Some(Rc::new(RefCell::new(root))));
  println!("{:?}", res);
}