二叉树的中序遍历

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

热度指数：87891 时间限制：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

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)