基本概念

二叉树

最常见的树即二叉树, 即每个结点最多只有两个子结点，分别为左子结点和右子结点。

二叉树的遍历

前序遍历：根结点 -> 左子树 -> 右子树
中序遍历：左子树 -> 根结点 -> 右子树
后序遍历：左子树 -> 右子树 -> 根结点

如何记忆？

1. 前中后都是指的是根结点被访问的顺序，标杆是根结点。前 -> 根结点第一个被访问，中 -> 根结点第二个被访问，后-> 根结点最后被访问。
2. 左子树总是在右子树之前。

Demo?
如下二叉树:

前序：
1 -> 2 -> 4 -> 5 -> 7 -> 8 -> 3 -> 6

中序:
4 -> 2 -> 7 -> 5 -> 8 -> 1 -> 3- > 6

后序：
4 -> 7 -> 8 -> 5 -> 2 -> 6 -> 3 -> 1

二叉树结点定义的代码

public class TreeNode {
    int val; // 结点的值
    TreeNode left; // 左结点
    TreeNode right; // 右结点
    TreeNode() {} // 空构造函数
    // 只指定值的构造函数，例如只有一个结点的树
    TreeNode(int val) {
        this.val = val;
    }
    // 指定val, left, right的构造函数
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}