AI创作问答(高级版)
在Java中，可以使用递归或迭代的方式来实现二叉树的遍历。
1. 前序遍历（Preorder traversal）：
- 递归实现：
```java
public void preOrderTraversal(TreeNode root) {
if (root != null) {
System.out.print(root.val + " "); // 先访问根节点
preOrderTraversal(root.left); // 再遍历左子树
preOrderTraversal(root.right); // 最后遍历右子树
}
}
```
- 迭代实现（使用栈）：
```java
public void preOrderTraversal(TreeNode root) {
if (root == null)
return;
Stack
stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.val + " "); // 访问当前节点
if (node.right != null)
stack.push(node.right); // 先将右子节点入栈
if (node.left != null)
stack.push(node.left); // 再将左子节点入栈
}
}
```
2. 中序遍历（Inorder traversal）：
- 递归实现：
```java
public void inOrderTraversal(TreeNode root) {
if (root != null) {
inOrderTraversal(root.left); // 先遍历左子树
System.out.print(root.val + " "); // 再访问根节点
inOrderTraversal(root.right); // 最后遍历右子树
}
}
```
- 迭代实现（使用栈）：
```java
public void inOrderTraversal(TreeNode root) {
Stack stack = new Stack<>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.left; // 不断将左子节点入栈，直到为空
}
node = stack.pop();
System.out.print(node.val + " "); // 访问当前节点
node = node.right; // 遍历右子树
}
}
```
3. 后序遍历（Postorder traversal）：
- 递归实现：
```java
public void postOrderTraversal(TreeNode root) {
if (root != null) {
postOrderTraversal(root.left); // 先遍历左子树
postOrderTraversal(root.right); // 再遍历右子树
System.out.print(root.val + " "); // 最后访问根节点
}
}
```
- 迭代实现（使用栈）：
```java
public void postOrderTraversal(TreeNode root) {
Stack stack = new Stack<>();
TreeNode curr = root;
TreeNode lastVisited = null;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left; // 不断将左子节点入栈，直到为空
}
TreeNode temp = stack.peek().right;
if (temp == null || temp == lastVisited) { // 当前节点的右子树为空或已经被访问过
curr = stack.pop();
System.out.print(curr.val + " "); // 访问当前节点
lastVisited = curr;
curr = null;
} else {
curr = temp; // 遍历右子树
}
}
}
```
希望以上答案能够满足您的需求。如果有任何疑问，请随时提出。
金宣小助手
官网微信公众号
