树与图简单2 种解法

#94二叉树的中序遍历

按左子树、根节点、右子树的顺序返回二叉树节点值。

#二叉树#深度优先搜索#栈

原题

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

查看原题

解题主线

递归写法直接对应“左—根—右”的定义。
迭代写法先沿左链入栈，弹出节点后再转向其右子树。

解法 1：递归中序遍历

把结果列表作为参数传入递归函数，依次访问左子树、当前节点和右子树。

时间复杂度： O(n)
空间复杂度： O(h)，递归栈深度为树高

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

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);
    }
}

解法 2：迭代中序遍历

用栈保存访问路径；左链到底后弹栈访问，再进入右子树。

时间复杂度： O(n)
空间复杂度： O(h)

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // 不变量：节点只在其左子树处理完毕后加入结果，再转向右子树。
        // 空树自然得到空列表；调用栈或显式栈仅保存尚未完成的访问路径。
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        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;
    }
}

边界与易错点

空树应返回空列表而不是 null。
迭代循环条件必须同时考虑当前节点和栈，否则会漏掉尚未处理的祖先。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/tree/Q094_tree_inorderTraversal.java
leetcode/src/main/java/tree/Q94_144_145_traversal.java