〇、定义

给出一种二叉树结点定义

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

一、二叉树前序遍历

前序遍历:先访问根结点，遍历左子树，再遍历右子树

LeetCode 144.二叉树前序遍历:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorder(root, result);
        return result;   
    }
   
    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) 
            return;
        result.add(root.val);//先访问根结点
        preorder(root.left, result);//再遍历左子树
        preorder(root.right, result);//遍历右子树
    }
}

二、二叉树中序遍历

中序遍历：先访问右子树，访问根结点，再遍历左子树

LeetCode 94.二叉树中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {  
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }
    
    public void inorder(TreeNode root, List<Integer> result) {
        if (root == null)
            return;
        inorder(root.left, result);
        result.add(root.val);
        inorder(root.right, result);
    }
}

三、二叉树后序遍历

后序遍历：先遍历右子树，遍历左子树，最后访问根结点

LeetCode 145.二叉树后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorder(root, result);
        return result;
    }
    
    public void postorder(TreeNode root, List<Integer> result) {
        if (root == null)
            return;
        postorder(root.left, result);
        postorder(root.right, result);
        result.add(root.val);
    }
}

总结：

用递归算法还是很好理解的。三种遍历相当于NLR、LNR、LRN，内部算法实现时只需要调换一下对根结点访问的位置。