mkdocs/docs/android面试/算法与数据结构/树与二叉树.md

树与二叉树

目录

• 树基础
• 二叉树基础
• 二叉树遍历
• 常见算法
• 面试常见问题

---

树基础

树定义

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

树术语

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

---

二叉树基础

二叉树定义

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

二叉树类型

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

---

二叉树遍历

前序遍历

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

中序遍历

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

后序遍历

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

层序遍历

// 按层遍历
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：二叉树的最大深度

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

题2：验证二叉搜索树

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年