二叉树遍历问题，总结递归和迭代解法

n node = stack.pop(); // 输出节点值 System.out.print(node.val + " "); // 先将右子节点入栈，因为栈是后进先出，保证顺序 if (node.right != null) { stack.push(node.right); } // 再将左子节点入栈 if (node.left != null) { stack.push(node.left); } } }四、中序遍历（左子树，根节点，右子树）1、递归实现：中序遍历的递归方式与前序类似，只是顺序变为左子树、根节点、右子树。private static void inOrderTraversal0(TreeNode root) { if (root == null) { return; } // 首先遍历左子树 inOrderTraversal0(root.left); // 打印根节点 System.out.print(root.val + " "); // 最后遍历右子树 inOrderTraversal0(root.right); }2、迭代实现：迭代方式通常使用栈，与前序遍历不同的是，先将左子节点入栈，再处理右子节点。private static void inOrderTraversal1(TreeNode root) { if (root == null) { return; } Stack<TreeNode> stack = new Stack<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); System.out.print(curr.val + " "); curr = curr.right; } }五、后序遍历（左子树，右子树，根节点）后序遍历相对复杂，递归实现相对直观，但迭代实现需要考虑更多的细节。1、递归实现：后序遍历的递归方式需要维护一个临时数组来记录访问过的节点，确保左右子树都被访问后再访问根节点。private static void postOrderTraversal0(TreeNode root) { if (root == null) { return; } postOrderTraversal0(root.left); postOrderTraversal0(root.right); // 最后打印根节点 System.out.print(root.val + " "); }2、迭代实现：迭代方法通常使用两个栈，一个用于存储待访问的节点，另一个用于暂存已访问的节点，以确保后序遍历的顺序。private static void postOrderTraversal1(TreeNode root) { if (root == null) { return; } Stack<TreeNode> stack1 = new Stack<>(), stack2 = new Stack<>(); stack1.push(root); while (!stack1.isEmpty()) { TreeNode node = stack1.pop(); stack2.push(node); if (node.left != null) { stack1.push(node.left); } if (node.right != null) { stack1.push(node.right); } } while (!stack2.isEmpty()) { System.out.print(stack2.pop().val + " "); } }总结二叉树的遍历是数据结构中的基础操作，理解递归和迭代解法对于解决更复杂的二叉树问题至关重要。递归方法简洁明了，易于理解，但可能会导致较大的函数调用开销。而迭代方法通常效率更高，但实现起来可能更复杂。在实际应用中，应根据具体需求和场景选择合适的遍历方式。通过练习和理解这些基本的遍历方法，可以为解决其他二叉树问题打下坚实的基础。