LeetCode题练习与总结：二叉树的中序遍历--94

一、题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

二、递归方法

（一）解题思路

1. 如果当前节点为空，返回。
2. 递归遍历左子树。
3. 访问当前节点，将节点的值添加到结果列表中。
4. 递归遍历右子树。

（二）具体代码

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();inorder(root, result);return result;}private void inorder(TreeNode node, List<Integer> result) {if (node == null) {return;}inorder(node.left, result);result.add(node.val);inorder(node.right, result);}
}

（三）时间复杂度和空间复杂度

1. 时间复杂度

• 递归方法会访问树中的每个节点恰好一次，因此时间复杂度与树中节点的数量成正比。
• 在这个算法中，每个节点都会被访问一次，所以时间复杂度是 O(n)，其中 n 是二叉树中的节点数。

2. 空间复杂度

• 递归方法的空间复杂度主要取决于递归栈的深度，这通常与树的高度成正比。
• 在最坏的情况下，树完全不平衡，每个节点都只有左子节点或者只有右子节点，递归栈的深度会达到节点数 n，因此空间复杂度为 O(n)。
• 在最好的情况下，树是完全平衡的，递归栈的深度是 log(n)，因此空间复杂度为 O(log(n))。
• 综合考虑，空间复杂度在最坏情况下是 O(n)，在最好情况下是 O(log(n))，平均情况下则介于两者之间。

综上所述，递归方法的中序遍历代码的时间复杂度是 O(n)，空间复杂度在最坏情况下是 O(n)，在最好情况下是 O(log(n))。

（四）总结知识点

1. 递归（Recursion）:

• 代码中使用了递归函数 inorder 来遍历二叉树的左子树、根节点和右子树。
• 递归是一种常用的算法设计技巧，它通过函数自身调用自己来进行循环。

2. 二叉树（Binary Tree）:

• 代码操作的数据结构是二叉树，每个节点包含一个值和指向左右子节点的引用。
• 二叉树是一种基础的数据结构，常用于各种算法问题。

3. 二叉树的中序遍历（Inorder Traversal of a Binary Tree）:

• 中序遍历是一种遍历二叉树的方法，按照“左-根-右”的顺序访问每个节点。
• 这是二叉树遍历的三种基本方法之一（其他两种是前序遍历和后序遍历）。

4. Java 集合框架（Java Collections Framework）:

• 代码使用了 ArrayList 来存储遍历的结果，这是 Java 集合框架中的一个类。
• ArrayList 是一个可调整大小的数组实现，提供了对元素的快速随机访问。

5. 函数定义和调用（Function Definition and Invocation）:

• 代码定义了两个函数：inorderTraversal 和 inorder。
• inorderTraversal 是公共方法，供外部调用；inorder 是私有辅助方法，用于递归遍历。

6. 基本语法（Basic Syntax）:

• 代码使用了基本的 Java 语法，如类定义、方法定义、条件语句（if）、返回语句（return）等。

7. 递归栈（Recursive Stack）:

• 虽然代码中没有显式使用栈数据结构，但递归函数在调用时会使用调用栈来存储每一层递归的状态。

三、迭代方法

（一）解题思路

1. 初始化一个空栈和一个空列表。
2. 将根节点及其所有左子节点入栈。
3. 弹出栈顶元素，将其值添加到结果列表中。
4. 将弹出节点的右子节点及其所有左子节点入栈。
5. 重复步骤3和4，直到栈为空。

（二）具体代码

import java.util.Stack;class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode current = root;while (current != null || !stack.isEmpty()) {while (current != null) {stack.push(current);current = current.left;}current = stack.pop();result.add(current.val);current = current.right;}return result;}
}

（三）时间复杂度和空间复杂度

1. 时间复杂度

• 中序遍历需要访问二叉树中的每个节点一次，因此时间复杂度与二叉树中节点的数量成正比。
• 在这个算法中，每个节点都会被访问一次，所以时间复杂度是 O(n)，其中 n 是二叉树中的节点数。

2. 空间复杂度

• 空间复杂度主要取决于迭代过程中使用的栈的大小。
• 在最坏的情况下，树完全不平衡，每个节点都只有左子节点或者只有右子节点，栈的大小会达到节点数 n，因此空间复杂度为 O(n)。
• 在最好的情况下，树是完全平衡的，栈的大小是 log(n)，因此空间复杂度为 O(log(n))。
• 综合考虑，空间复杂度在最坏情况下是 O(n)，在最好情况下是 O(log(n))，平均情况下则介于两者之间。

综上所述，这段代码的时间复杂度是 O(n)，空间复杂度在最坏情况下是 O(n)，在最好情况下是 O(log(n))。

（四）总结知识点

1. 迭代（Iteration）:

• 代码使用了一个循环结构来迭代地遍历二叉树的节点，而不是使用递归。

2. 栈（Stack）数据结构:

• 代码使用了一个 Stack 来存储访问过的节点，以便后续能够按照正确的顺序访问它们的右子节点。
• 栈是一种后进先出（LIFO）的数据结构，非常适合用于这种需要回溯的场景。

3. 二叉树（Binary Tree）:

• 代码操作的数据结构是二叉树，每个节点包含一个值和指向左右子节点的引用。
• 二叉树是一种基础的数据结构，常用于各种算法问题。

4. 二叉树的中序遍历（Inorder Traversal of a Binary Tree）:

• 中序遍历是一种遍历二叉树的方法，按照“左-根-右”的顺序访问每个节点。
• 这是二叉树遍历的三种基本方法之一（其他两种是前序遍历和后序遍历）。

5. Java 集合框架（Java Collections Framework）:

• 代码使用了 ArrayList 来存储遍历的结果，这是 Java 集合框架中的一个类。
• ArrayList 是一个可调整大小的数组实现，提供了对元素的快速随机访问。
• 同时，代码使用了 Stack 类来实现栈数据结构。

6. 循环和条件语句（Loop and Conditional Statements）:

• 代码使用了 while 循环来迭代遍历树节点，并使用了 if 语句来检查当前节点是否为空。

7. 函数定义和调用（Function Definition and Invocation）:

• 代码定义了一个公共方法 inorderTraversal，供外部调用。

8. 基本语法（Basic Syntax）:

• 代码使用了基本的 Java 语法，如类定义、方法定义、循环结构、条件语句等。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。