树

        1          ← 根节点 (root)
       / \
      2   3        ← 1的子节点，2和3互为兄弟节点
     / \
    4   5          ← 叶节点 (没有子节点)

• 节点: 树中的每个元素
• 根节点: 最顶部，没有父节点
• 叶节点: 没有子节点
• 高度/深度: 根到最远叶节点的层数，上面的树是3
• 二叉树: 每个节点最多有2个子节点

遍历方式

总结: 前中后 指的是根节点的访问顺序，左永远在右的前面。

• 前序遍历: 根 -> 左 -> 右
• 中序遍历: 左 -> 根 -> 右
• 后序遍历: 左 -> 右 -> 根

遍历代码实现

递归

class TreeNode(val `val`: Int, var left: TreeNode? = null, var right: TreeNode? = null)

// 前序
fun preorder(root: TreeNode?) {
    if (root == null) return
    print(root.`val`)   // 根
    preorder(root.left)  // 左
    preorder(root.right) // 右
}

// 中序
fun inorder(root: TreeNode?) {
    if (root == null) return
    inorder(root.left)   // 左
    print(root.`val`)    // 根
    inorder(root.right)  // 右
}

// 后序
fun postorder(root: TreeNode?) {
    if (root == null) return
    postorder(root.left)  // 左
    postorder(root.right) // 右
    print(root.`val`)     // 根
}

三种遍历方式的唯一区别就是根节点的print那一行的位置。