二叉树的基础

主要有满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树。

满二叉树：如果一棵二叉树只有度为0或2的节点，且度为0的节点在同一层则为满二叉树。满二叉树的深度为k，则节点数为2^k-1。

完全二叉树：在完全二叉树的基础上，最后一层叶子结点都在最左边的位置。

二叉搜索树（二叉排序树、二叉查找树）：是一个有序树；左子树的所有节点值均小于根节点值；右子树的所有节点值均大于根节点值；左右子树也分别为二叉搜索树。

平衡二叉搜索树：在二叉搜索树的基础上有以下性质：为空树或者左右两个子树的高度差的绝对值不超过1，且左右子树也分别为平衡二叉搜索树。

二叉堆：是完全二叉树，同时保证父子节点的顺序关系。优先队列就是一个堆。

主要为：链式存储（链表），顺序存储（数组）。

堆的实现就是基于数组实现的，按照层序遍历的方式依次存入数组下标。

遍历方式主要有两种：

1.深度优先遍历（DFS）：先往深处走，遇到叶子结点再往回走。

• 前序遍历（递归法，迭代法）中—>左—>右
• 中序遍历（递归法，迭代法）左—>中—>右
• 后序遍历（递归法，迭代法）左—>右—>中

        这里的前中后指的是中间结点的遍历顺序。

2.广度优先搜索（BFS）：一层一层的遍历。

DFS深度优先搜索经常会使用递归的方式来实现，但是也可以借助栈使用非递归的方式来实现的。（栈其实就是递归的一种实现结构）

BFS广度优先搜索一般是使用队列来实现的，这也是由队列的先进先出的特点来决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode() {
    }
    
    public TreeNode(int val) {
        this.val = val;
    }

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