JAVA二刷-Day14 | 144.二叉树的前序遍历, 145.二叉树的后序遍历, 94.二叉树的中序遍历

**JAVA二刷-Day14 | 二叉树的前序、后序、中序遍历**

在本篇文章中，我们将讨论如何实现二叉树的前序、后序和中序遍历。这些遍历是通过递归或迭代方式来访问二叉树中的每个节点。

###1. 前序遍历前序遍历是指先访问根节点，然后再访问左子树和右子树。

java// Definition for a binary tree node.
public class TreeNode {
 int val;
 TreeNode left;
 TreeNode right;
 TreeNode(int x) { val = x; }
}

class Solution {
 public List preorderTraversal(TreeNode root) {
 List res = new ArrayList<>();
 if (root == null) return res;

 // 前序遍历的顺序是根节点 -> 左子树 -> 右子树 res.add(root.val);
 res.addAll(preorderTraversal(root.left));
 res.addAll(preorderTraversal(root.right));

 return res;
 }
}

javaclass Solution {
 public List postorderTraversal(TreeNode root) {
 List res = new ArrayList<>();
 if (root == null) return res;

 // 后序遍历的顺序是左子树 -> 右子树 -> 根节点 res.addAll(postorderTraversal(root.left));
 res.addAll(postorderTraversal(root.right));
 res.add(root.val);

 return res;
 }
}

javaclass Solution {
 public List inorderTraversal(TreeNode root) {
 List res = new ArrayList<>();
 if (root == null) return res;

 // 中序遍历的顺序是左子树 -> 根节点 -> 右子树 res.addAll(inorderTraversal(root.left));
 res.add(root.val);
 res.addAll(inorderTraversal(root.right));

 return res;
 }
}

javapublic class Main {
 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("前序遍历:");
 List preorder = preorderTraversal(root);
 for (int i : preorder) {
 System.out.print(i + " ");
 }
 System.out.println();

 // 后序遍历 System.out.println("后序遍历:");
 List postorder = postorderTraversal(root);
 for (int i : postorder) {
 System.out.print(i + " ");
 }
 System.out.println();

 // 中序遍历 System.out.println("中序遍历:");
 List inorder = inorderTraversal(root);
 for (int i : inorder) {
 System.out.print(i + " ");
 }
 }

 public static List preorderTraversal(TreeNode root) {
 // ...
 }

 public static List postorderTraversal(TreeNode root) {
 // ...
 }

 public static List inorderTraversal(TreeNode root) {
 // ...
 }
}