# 树与二叉树

## 目录
- [树基础](#树基础)
- [二叉树基础](#二叉树基础)
- [二叉树遍历](#二叉树遍历)
- [常见算法](#常见算法)
- [面试常见问题](#面试常见问题)

---

## 树基础

### 树定义

```java
// 树：由节点和边组成的非线性数据结构
public class TreeNode {
    int val;
    List<TreeNode> children;
}
```

### 树术语

```java
// 1. 节点：树中的元素
// 2. 根节点：最顶层节点
// 3. 叶子节点：没有子节点的节点
// 4. 深度：从根到节点的路径长度
// 5. 高度：树的最大深度
```

---

## 二叉树基础

### 二叉树定义

```java
// 二叉树：每个节点最多有两个子节点
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
}
```

### 二叉树类型

```java
// 1. 满二叉树：所有节点都有两个子节点
// 2. 完全二叉树：除了最后一层，其他层都是满的
// 3. 二叉搜索树：左子树 < 根 < 右子树
// 4. 平衡二叉树：左右子树高度差不超过 1
```

---

## 二叉树遍历

### 前序遍历

```java
// 根 → 左 → 右
public void preorder(TreeNode root) {
    if (root == null) return;
    System.out.println(root.val);
    preorder(root.left);
    preorder(root.right);
}
```

### 中序遍历

```java
// 左 → 根 → 右
public void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.println(root.val);
    inorder(root.right);
}
```

### 后序遍历

```java
// 左 → 右 → 根
public void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.println(root.val);
}
```

### 层序遍历

```java
// 按层遍历
public void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.val);
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}
```

---

## 常见算法

### 题1：二叉树的最大深度

```java
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
```

### 题2：验证二叉搜索树

```java
public boolean isValidBST(TreeNode root) {
    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean isValidBST(TreeNode root, long min, long max) {
    if (root == null) return true;
    if (root.val <= min || root.val >= max) return false;
    return isValidBST(root.left, min, root.val) &&
           isValidBST(root.right, root.val, max);
}
```

---

## 面试常见问题

### Q1: 二叉树的遍历方式？

**答案：**
1. 前序遍历：根 → 左 → 右
2. 中序遍历：左 → 根 → 右
3. 后序遍历：左 → 右 → 根
4. 层序遍历：按层遍历

### Q2: 二叉搜索树的特点？

**答案：**
- 左子树所有节点 < 根节点
- 右子树所有节点 > 根节点
- 中序遍历是有序的

---

*最后更新：2024年*
