二叉树

一、二叉树基础定义

二叉树是每个节点最多有两个子节点的树结构，子节点分别称为左子节点和右子节点，且左、右子树也分别满足二叉树的定义。

• 节点不强制同时拥有两个子节点，可仅含左子节点或右子节点
• 物理存储可分为链式存储和数组存储两种方式

链式存储节点结构

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. 二叉搜索树（BST）：有序二叉树，满足左子树节点值 < 根节点值 < 右子树节点值
4. 红黑树：自平衡二叉搜索树，通过颜色标记和旋转操作维持树的平衡，避免退化为链表

---

三、二叉搜索树（BST）详解

1. 核心定义

二叉搜索树（Binary Search Tree，BST）又称二叉查找树，是一种有序二叉树，满足以下性质：

• 任意节点的左子树中所有节点值 < 该节点值
• 任意节点的右子树中所有节点值 > 该节点值
• 树中无键值相等的节点

2. 时间复杂度分析

• 平均情况：树结构平衡时，插入、查找、删除操作的时间复杂度为 O(log n)
• 最坏情况：树退化为链表（如按顺序插入有序数据），操作时间复杂度为 O(n)

3. 优缺点

• 优点：有序存储，查找效率高（平衡状态下），支持中序遍历获取有序序列
• 缺点：极端情况下会退化为链表，性能大幅下降，需额外的平衡机制（如红黑树）优化

---

四、面试高频问题解析

1. 问：什么是二叉树？答： 二叉树是每个节点最多有两个子节点的树结构，子节点分为左、右子节点，且左右子树也满足二叉树定义。节点可仅含单个子节点，存储方式包括链式存储和数组存储。

2. 问：二叉搜索树的定义是什么？时间复杂度如何？答： 二叉搜索树是有序二叉树，满足左子树节点值 < 根节点值 < 右子树节点值，无重复节点。平均情况下插入、查找、删除时间复杂度为O(log n)，最坏情况下退化为链表，时间复杂度为O(n)。

3. 问：二叉搜索树的缺点是什么？如何解决？答： 缺点是极端情况下会退化为链表，导致操作效率下降。可通过自平衡二叉搜索树（如红黑树、AVL树）解决，通过颜色标记、旋转操作维持树的平衡，保证时间复杂度稳定在O(log n)。

4. 问：链式存储和数组存储二叉树的区别是什么？答： 链式存储通过节点的left/right指针关联，结构灵活，适合任意二叉树；数组存储通过下标计算父子节点位置（父节点i的左子节点为2i+1，右子节点为2i+2），仅适合完全二叉树，访问效率高但空间利用率低。