[Vssue]二叉树理论基础.md

[youngyangyang04]

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

[jzlhk]

Full binary tree叶子节点不一定需要在同一层吧？

[Du1in9]

二叉树的种类

• 满二叉树

如果一棵二叉树只有度为 0 和 2 的结点，并且度为 0 的结点在同一层上，则这棵二叉树为满二叉树。深度为 k，有 2^k-1个节点。

• 完全二叉树

除了最底层节点可能没填满外（且集中在左侧），其余每层节点数都填满。若最底层为第 h 层，则该层最多 2^(h-1) 个节点。

我们刚刚讲过的优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

• 二叉搜索树

前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。

• 平衡二叉搜索树

平衡二叉搜索树，又称 AVL 树，它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1。

C++ 中 map、set、multimap，multiset 的底层实现是平衡二叉搜索树（红黑树），所以增删查操作时间复杂度是 O(log n)

Java 中 TreeMap、TreeSet 的底层实现是平衡二叉搜索树（红黑树），所以增删查操作时间复杂度是 O(log n)

二叉树的存储方式

① 链式存储：用指针表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。

② 顺序存储：用数组表示的二叉树如何遍历呢？如果父节点下标是 i，那么左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

二叉树的遍历方式

1. 深度优先遍历（DFS）：借助栈使用递归的方式来实现
   • 前序遍历、中序遍历、后序遍历（递归法，迭代法）
2. 广度优先遍历（BFS）：借助队列先进先出的特点来实现
   • 层次遍历（迭代法）

二叉树的定义

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 的时候，节点默认都定义好了，真到面试的时候需要自己手写，有时候会一脸懵逼！