Function leetcode_for_rust::cd0094_binary_tree_inorder_traversal::inorder_traversal

pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32>

Solutions

Approach 1: Recursive Approach

• Time complexity: O(n)

• Space complexity: O(logn)

• Runtime: 0 ms

• Memory: 2.4 MB

// 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;
impl Solution {
    pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut result: Vec<i32> = vec![];
        if root.is_none() { return result; }

        Self::_in_order(root, &mut result);
        result
    }
    fn _in_order(root: Option<Rc<RefCell<TreeNode>>>, result: &mut Vec<i32>) {
        match root {
            Some(node) => {
                Self::_in_order(node.borrow().left.clone(), result);
                result.push(node.borrow().val);
                Self::_in_order(node.borrow().right.clone(), result);
            },
            None => { return; }
        }
    }
}

Approach 2: Iterating method using Stack

• Time complexity: O(n)

• Space complexity: O(n)

• Runtime: 0 ms

• Memory: 2.4 MB

// 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;
impl Solution {
    pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut result = vec![];
        if root.is_none() { return result; }

        let mut stack = Vec::new();
        let mut r = root.clone();

        while r.is_some() || !stack.is_empty() {
            while let Some(node) = r {
               stack.push(node.clone());
               r = node.borrow().left.clone();
            }
            r = stack.pop();
            if let Some(node) = r {
                result.push(node.borrow().val);
                r = node.borrow().right.clone();
            }
        }
        result
    }
}