手撸二叉树之二叉树的中序遍历

手撸二叉树之二叉树的中序遍历

今天给大家带来的关于二叉树相关的算法题是求二叉树的中序遍历，正文如下：

题目

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

示例1：

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

示例2：

输入：root = []输出：[]

示例3：

输入：root = [1]输出：[1]

示例4：

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

解题思路

使用递归

首先使用递归的方式来求解此题是最方便，最快捷的手段；二叉树的中序遍历的顺序为：访问左子树，访问根节点，访问右节点；当前节点为空时，终止。因为此题要求返回的是一个 List 数组，所以在递归的时候，遇到 root 节点，就将其加入到数组中，最后数组的内容即为中序遍历的结果.

代码实现

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List inorderTraversal(TreeNode root) { List res = new ArrayList(); inorder(root, res); return res; } public void inorder(TreeNode root, List res) { if (root == null) { return; } // 访问左子树 inorder(root.left, res); // 访问根节点 res.add(root.val); // 访问右子树

最后

复杂度分析

时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。