java/InOrderTraversal.java

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class InOrderTraversal {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);

        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        List<Integer> result = inOrderTraversal(root);
        System.out.println(result); // 输出: [4, 2, 5, 1, 3]

        List<Integer> result2 = inOrderTraversalNonRecursive(root);
        System.out.println(result2); // 输出: [4, 2, 5, 1, 3]
    }

    // 中序遍历二叉树
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // 递归中序遍历方法
    public static List<Integer> inOrderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        forEach(root, result);
        return result;
    }

    public static void forEach(TreeNode node, List<Integer> result) {
        if (node != null) {
            // 左子树
            forEach(node.left, result);
            // 处理节点数据
            result.add(node.val);
            // 右子树
            forEach(node.right, result);
        }
    }

    // 非递归中序遍历方法
    public static List<Integer> inOrderTraversalNonRecursive(TreeNode root) {
        if (root == null) {
            return null;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        List<Integer> result = new ArrayList<>();

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

}