94. Binary Tree Inorder Traversal Easy

1/**
2 * [94] Binary Tree Inorder Traversal
3 *
4 * Given the root of a binary tree, return the inorder traversal of its nodes' values.
5 *  
6 * Example 1:
7 * <img alt="" src="https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg" style="width: 125px; height: 200px;" />
8 * Input: root = [1,null,2,3]
9 * Output: [1,3,2]
10 *
11 * Example 2:
12 *
13 * Input: root = []
14 * Output: []
15 *
16 * Example 3:
17 *
18 * Input: root = [1]
19 * Output: [1]
20 *
21 *  
22 * Constraints:
23 *
24 * The number of nodes in the tree is in the range [0, 100].
25 * -100 <= Node.val <= 100
26 *
27 *  
28 * Follow up: Recursive solution is trivial, could you do it iteratively?
29 */
30pub struct Solution {}
31#[allow(unused_imports)]
32use crate::util::tree::{to_tree, TreeNode};
33
34// problem: https://leetcode.com/problems/binary-tree-inorder-traversal/
35// discuss: https://leetcode.com/problems/binary-tree-inorder-traversal/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39// Definition for a binary tree node.
40// #[derive(Debug, PartialEq, Eq)]
41// pub struct TreeNode {
42//   pub val: i32,
43//   pub left: Option<Rc<RefCell<TreeNode>>>,
44//   pub right: Option<Rc<RefCell<TreeNode>>>,
45// }
46//
47// impl TreeNode {
48//   #[inline]
49//   pub fn new(val: i32) -> Self {
50//     TreeNode {
51//       val,
52//       left: None,
53//       right: None
54//     }
55//   }
56// }
57use std::cell::RefCell;
58use std::rc::Rc;
59type Node = Option<Rc<RefCell<TreeNode>>>;
60impl Solution {
61    pub fn inorder_traversal(root: Node) -> Vec<i32> {
62        Self::traversal(&root)
63    }
64
65    fn traversal(node: &Node) -> Vec<i32> {
66        let mut result = vec![];
67        if let Some(n) = node {
68            let nf = n.as_ref().borrow();
69            result.append(&mut Self::traversal(&nf.left));
70            result.push(nf.val);
71            result.append(&mut Self::traversal(&nf.right));
72        }
73
74        result
75    }
76}
77
78// submission codes end
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83    use crate::tree;
84
85    #[test]
86    fn test_94() {
87        assert_eq!(
88            Solution::inorder_traversal(tree![1, null, 2, 3]),
89            vec![1, 3, 2]
90        );
91    }
92}
93