如何实现二叉树的遍历算法？

二叉树的遍历是非常常见和重要的操作。主要有前序遍历、中序遍历和后序遍历三种方式。

我们可以使用递归方式实现二叉树的三种遍历:

public void preOrder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preOrder(root.left);
    preOrder(root.right);
}

public void inOrder(TreeNode root) {
    if (root == null) return;
    inOrder(root.left);
    System.out.print(root.val + " ");
    inOrder(root.right); 
}  

public void postOrder(TreeNode root) {
    if (root == null) return;
    postOrder(root.left);  
    postOrder(root.right);
    System.out.print(root.val + " ");
}

三种遍历的流程如下:

• 前序遍历:根节点 -> 左子树 -> 右子树
• 中序遍历:左子树 -> 根节点 -> 右子树
• 后序遍历:左子树 -> 右子树 -> 根节点

所以,二叉树遍历的关键在于:

• 1. 递归函数首先要判断树空的base case,否则会栈溢出。
• 2. 前序遍历先访问根节点,然后遍历左子树和右子树。
• 3. 中序遍历先遍历左子树,然后访问根节点,最后遍历右子树。
• 4. 后序遍历先遍历左子树和右子树,最后访问根节点。
• 5. 用一个变量记录遍历到的节点的值,并在函数最后打印。