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

  • Johnathan
  • 更新于 2023-01-19 09:05
  • 阅读 212

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

问题描述

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

解题思路

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

  • Option可以采用Some或者.map来进行模式匹配,对里面的数据解包,有几层Option就采用几层Some.map
  • 对于Box<T>和Rc<T>而言其所有的数据T,由于存在自动解引用,可以直接采用普通引用的所有操作(调用方法或获取属性),因此可以认为这两者对于T是透明的;但是对于Rc<RefCell<T>>>则不一样了,RefCell需要先通过borrowborrow_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&lt;Rc&lt;RefCell&lt;TreeNode>>>,
  pub right: Option&lt;Rc&lt;RefCell&lt;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&lt;Rc&lt;RefCell&lt;TreeNode>>>) -> Vec&lt;i32> {
      let mut res = vec![];
      // Solution::recursive(root, &mut res);
      Solution::iterate(root, &mut res);
      res
    }

    fn recursive(root: Option&lt;Rc&lt;RefCell&lt;TreeNode>>>, res: &mut Vec&lt;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&lt;Rc&lt;RefCell&lt;TreeNode>>>, res: &mut Vec&lt;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);
}

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
Johnathan
Johnathan - PhD

29 篇文章, 1352 学分