Function leetcode_for_rust::cd0145_binary_tree_postorder_traversal::postorder_traversal

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

        Self::_post_order(root, &mut result);
        result
    }
    fn _post_order(root: Option<Rc<RefCell<TreeNode>>>, result: &mut Vec<i32>) {
        match root {
            Some(node) => {
                Self::_post_order(node.borrow().left.clone(), result);
                Self::_post_order(node.borrow().right.clone(), result);
                result.push(node.borrow().val);
            },
            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 postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut result = vec![];
        if root.is_none() { return result; }

        let mut stack1: Vec<Option<Rc<RefCell<TreeNode>>>> = Vec::new();
        let mut stack2: Vec<Option<Rc<RefCell<TreeNode>>>> = Vec::new();
        stack1.push(root);

        while let Some(Some(node)) = stack1.pop() {
            if node.borrow().left.is_some() {
                stack1.push(node.borrow().left.clone());
            }
            if node.borrow().right.is_some() {
                stack1.push(node.borrow().right.clone());
            }
            stack2.push(Some(node));
        }

        while let Some(Some(node)) = stack2.pop() {
           result.push(node.borrow().val);
        }

        result
    }
}