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

一、题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

二、递归方法

（一）解题思路

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

（二）具体代码

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）:

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

三、迭代方法

（一）解题思路

初始化一个空栈和一个空列表。
将根节点及其所有左子节点入栈。
弹出栈顶元素，将其值添加到结果列表中。
将弹出节点的右子节点及其所有左子节点入栈。
重复步骤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;
    }
}