二叉树的中序遍历

[编程题]二叉树的中序遍历

热度指数：112321 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树的根节点root，返回它的中序遍历结果。

数据范围：树上节点数满足 $0 \le n \le 1000$ ，树上每个节点的值满足 $-1000 \le val \le 1000$
进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,#,#,3}

输出

[2,3,1]

说明

示例2

输入

{}

输出

[]

示例3

输入

{1,2}

输出

[2,1]

说明

示例4

输入

{1,#,2}

输出

[1,2]

说明

备注:

树中节点数目在范围 [0, 100] 内
树中的节点的值在[-100,100]以内

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Rust

老刘001

/**
 * #[derive(PartialEq, Eq, Debug, Clone)]
 * pub struct TreeNode {
 *     pub val: i32,
 *     pub left: Option<Box<TreeNode>>,
 *     pub right: Option<Box<TreeNode>>,
 * }
 *
 * impl TreeNode {
 *     #[inline]
 *     fn new(val: i32) -> Self {
 *         TreeNode {
 *             val: val,
 *             left: None,
 *             right: None,
 *         }
 *     }
 * }
 */
struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param root TreeNode类 
        * @return int整型一维数组
    */
    pub fn inorderTraversal(&self, root: Option<Box<TreeNode>>) -> Vec<i32> {
        // write code here
        let mut v = Vec::new();
        self.f(root, &mut v);
        v
    }

    fn f(&self,mut node: Option<Box<TreeNode>>, v: &mut Vec<i32>)  {
        if node.is_none() {return}
        self.f(node.as_mut().unwrap().left.take(), v);
        v.push(node.as_mut().unwrap().val);
        self.f(node.as_mut().unwrap().right.take(), v);
    }
}

发表于 2024-08-15 23:05:04 回复(0)

Rust

clever-kalamh7o

struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    pub fn inorderTraversal(&self, root: Option<Box<TreeNode>>) -> Vec<i32> {
        // write code here
        let mut res = vec![];

        fn dfs(node: &Option<Box<TreeNode>>, arr: &mut Vec<i32>) {
            if let Some(ref node) = *node {
                dfs(&node.left, arr);
                arr.push(node.val);
                dfs(&node.right, arr);
            }
        }

        dfs(&root, &mut res);
        res
    }
}

发表于 2024-03-06 12:22:56 回复(0)