树与图简单2 种解法

#94二叉树的中序遍历

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

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

解题主线

递归写法直接对应“左—根—右”的定义。

迭代写法先沿左链入栈，弹出节点后再转向其右子树。

解法 1：递归中序遍历

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

时间复杂度

O(n)

空间复杂度

O(h)，递归栈深度为树高

94. 二叉树的中序遍历 · 递归中序遍历

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)

94. 二叉树的中序遍历 · 迭代中序遍历

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.javaleetcode/src/main/java/tree/Q94_144_145_traversal.java