java二叉树中序遍历

### Java实现二叉树中序遍历 #### 方法一：递归实现 递归是一种直观且易于理解的方式来实现二叉树的中序遍历。以下是基于递归方式的具体代码示例： ```java public class BinaryTree { public static void inOrder(TreeNode root) { if (root == null) { return; } // 递归访问左子树 inOrder(root.left); // 访问根节点 System.out.print(root.val + " "); // 递归访问右子树 inOrder(root.right); } public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } } ``` 上述代码展示了如何通过递归的方式完成二叉树的中序遍历[^3]。 --- #### 方法二：迭代实现 对于不希望使用递归或者受限于递归调用栈的情况，可以采用迭代法来实现中序遍历。这种方法通常借助显式的栈数据结构来模拟递归过程。 以下是具体的迭代实现代码： ```java import java.util.ArrayList; import java.util.List; import java.util.Stack; public class BinaryTreeIteration { public static 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; } public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } } ``` 这段代码实现了利用栈进行迭代的中序遍历逻辑[^2]。 --- #### 示例输入与输出 假设有一个如下所示的二叉树： ``` 1 / \ 2 3 / \ 4 5 ``` 对应的中序遍历结果应为 `4 2 5 1 3`。 可以通过以下测试代码验证两种方法的结果一致性： ```java 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); // 使用递归方法打印中序遍历 System.out.println("Recursive Inorder Traversal:"); inOrder(root); // 使用迭代方法获取中序遍历列表 System.out.println("\nIterative Inorder Traversal:"); List<Integer> iterativeResult = inorderTraversal(root); for (int value : iterativeResult) { System.out.print(value + " "); } } ``` 以上代码分别演示了递归和迭代两种方法的应用场景及其输出效果。 ---