java二叉树遍历怎么写
时间: 2023-03-23 20:04:01 浏览: 52
Java二叉树遍历可以使用递归或迭代的方式实现。常见的遍历方式包括前序遍历、中序遍历和后序遍历。
1. 前序遍历:先访问根节点,再访问左子树,最后访问右子树。
递归实现:
```
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
```
迭代实现:
```
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> 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. 中序遍历:先访问左子树,再访问根节点,最后访问右子树。
递归实现:
```
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
```
迭代实现:
```
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> 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. 后序遍历:先访问左子树,再访问右子树,最后访问根节点。
递归实现:
```
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
```
迭代实现:
```
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> 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 + " ");
}
}
```