二叉树中序遍历的递归与迭代解法

"二叉树的中序遍历算法实现" 二叉树的中序遍历是一种常见的遍历策略，它按照左子树-根节点-右子树的顺序访问二叉树的所有节点。这种遍历方式对于查找二叉树中的特定属性（如查找排序序列）或构建某种数据结构（如堆）特别有用。在这个问题中，我们被要求返回给定二叉树的中序遍历结果。 ### 方法1：递归解析 递归是最直观的方法来实现中序遍历。基本思路是： 1. 定义一个递归函数`inorder(root)`，该函数接受一个二叉树节点`root`作为参数。 2. 首先，我们递归地处理`root`的左子树，即调用`inorder(root.left)`。 3. 接着，我们将`root`的值添加到结果列表中。 4. 最后，我们处理`root`的右子树，即调用`inorder(root.right)`。 5. 当遇到空节点时，递归结束。 ```java class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); inorder(root, res); return res; } private void inorder(TreeNode root, List<Integer> res) { if (root == null) { return; } inorder(root.left, res); res.add(root.val); inorder(root.right, res); } } ``` ### 复杂度分析 - **时间复杂度**：$O(n)$，其中$n$为二叉树的节点数。每个节点只被访问一次。 - **空间复杂度**：$O(n)$，最坏情况下，当二叉树退化为链表时，递归深度将达到$n$，占用$O(n)$的栈空间。 ### 方法2：迭代解析 迭代法通常使用栈来模拟递归过程。基本步骤如下： 1. 创建一个空栈，并初始化一个结果列表。 2. 当二叉树非空时，循环执行以下操作： - 如果当前节点非空，将其压入栈中，并移动到其左子节点。 - 否则，栈顶元素即为当前节点。访问该节点（将其值添加到结果列表），然后将当前节点设置为其右子节点。 3. 循环结束后，遍历完成。 ```java class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Deque<TreeNode> stk = new LinkedList<>(); while (root != null || !stk.isEmpty()) { while (root != null) { stk.push(root); root = root.left; } root = stk.pop(); res.add(root.val); root = root.right; } return res; } } ``` ### 结论 两种方法都能有效地解决二叉树的中序遍历问题。递归方法简洁明了，但可能会导致较大的栈空间消耗。迭代方法虽然代码相对复杂，但可以节省栈空间，尤其在处理深度较大的二叉树时更优。在实际应用中，应根据具体场景选择合适的方法。