二叉树理论基础

代码随想录

https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

二叉树的种类

满二叉树：其一定是完全二叉树
满二叉树的节点数量为 2的k次方-1

完全二叉树：
除了底层以外，其他层都是满的，并且底层是从左到右连续的

二叉搜索树：元素是有序的，查询是 log n 级别的，
其不是完全二叉树，不需要遵循完成二叉树的相关限制

平衡二叉搜素树 ： 左子树的层数 与 右子树的层数 的高度差不能超过1

存储方式

链式存储：
链表

线式存储：
数组

二叉树的遍历

深度优先搜索

前、中、后序优先搜索

递归法，迭代法

前、中、后序的区别：遍历的中节点放在那个位置上
前： 中 左 右
中： 左 中 右
后： 左 右 中

广度优先搜索

层序遍历，一层一层去遍历

二叉树的定义

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;
    }
}

递归遍历三步走

1、确认递归函数的参数和返回值
2、确定终止条件
3、确认单层递归的逻辑

全面理解递归