专栏首页用户画像Leetcode No.94 二叉树的中序遍历

Leetcode No.94 二叉树的中序遍历

一、题目描述

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

示例 1:

输入:root = [1,null,2,3] 输出:[1,3,2]

示例 2: 输入:root = [] 输出:[]

示例 3: 输入:root = [1] 输出:[1]

示例 4:

输入:root = [1,2] 输出:[2,1]

示例 5:

输入:root = [1,null,2] 输出:[1,2]

提示:

树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100

二、解题思路

首先我们需要了解什么是二叉树的中序遍历:按照访问左子树——根节点——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候我们按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,我们可以直接用递归函数来模拟这一过程。

定义 inorder(root) 表示当前遍历到 root 节点的答案,那么按照定义,我们只要递归调用 inorder(root.left) 来遍历root 节点的左子树,然后将root 节点的值加入答案,再递归调用inorder(root.right) 来遍历 root 节点的右子树即可,递归终止的条件为碰到空节点。

三、代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> rs;
        inorder(root,rs);
        return rs;
    }
    void inorder(TreeNode* root,vector<int> &rs){
        if(root==nullptr){
            return;
        }
        inorder(root->left,rs);
        rs.push_back(root->val);
        inorder(root->right,rs);
    }
};

四、复杂度分析

时间复杂度:O(n),其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

空间复杂度:O(n)。空间复杂度取决于递归的栈深度,而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 94. 二叉树的中序遍历(中序遍历)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-tree-inorder-travers...

    Michael阿明
  • LeetCode | 94.二叉树的中序遍历

    这次来写一下 LeetCode 的第 94 题,二叉树的中序遍历。

    码农UP2U
  • 94. 二叉树的中序遍历

    CaesarChang张旭
  • LeetCode144.二叉树的前序遍历&94.二叉树的中序遍历&145.二叉树的后序遍历

     后序遍历的非递归代码得说一下,首先后序遍历得顺序是左右中,我们知道先序遍历的压栈顺序是先压右再压左,这样出来的顺序就是中左右,如果把先序遍历的压栈顺序稍微变一...

    mathor
  • ​LeetCode刷题实战94:二叉树的中序遍历

    https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

    程序IT圈
  • LeetCode 94:二叉树的中序遍历 Binary Tree Inorder Traversal

    Given a binary tree, return the inorder traversal of its nodes' values.

    爱写bug
  • ​LeetCode刷题实战98:验证二叉搜索树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • LC94–二叉树的中序遍历—144. 二叉树的前序遍历

    LC94--二叉树的中序遍历---144. 二叉树的前序遍历 ...

    Java架构师必看
  • LC94–二叉树的中序遍历—144. 二叉树的前序遍历

    Java架构师必看
  • C++版 - Leetcode 94:Binary Tree Inorder Traversal (二叉树中序遍历,非递归)

    提交地址: https://leetcode.com/problems/binary-tree-inorder-traversal/

    Enjoy233
  • LeetCode 94 | 基础题,如何不用递归中序遍历二叉树?

    今天是LeetCode专题第60篇文章,我们一起来看的是LeetCode的94题,二叉树的中序遍历。

    TechFlow-承志
  • LeetCode 144. 二叉树的前序遍历(前序遍历)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-tree-preorder-traver...

    Michael阿明
  • 二叉树中序遍历

    二叉树是一种排序的基本的数据结构,而如果要想为多个对象进行排序,那么就必须可以区分出对象的大小,那么就必须依靠Comparable接口完成。 二叉树的基本原理...

    葆宁
  • 二叉树遍历问题-LeetCode 144、94、145、102、987(前序,中序,后序,层次,垂序)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-tree-preorder-travers...

    算法工程师之路
  • 【leetcode刷题】T111-二叉树的中序遍历

    木又AI帮
  • 【每日leetcode】20.二叉树的中序遍历

    树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100

    一条IT
  • LeetCode 102. 二叉树的层序遍历

    给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。

    TrueDei
  • LeetCode1-120题汇总,希望对你有点帮助!

    时间很快,公众号发布的LeetCode题目,已经达到120道题了。今天把发布的1-120篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相...

    程序IT圈
  • [数据结构] 二叉树的前序遍历、中序遍历和后序遍历

    泰坦HW

扫码关注云+社区

领取腾讯云代金券