CS61B 课程笔记（Examprep 10 Heaps and Graphs Exam Prep)

1. 操作理解（An Operational Understanding）

1.1 二叉搜索树（BST）的性质

在二叉搜索树中，左子树的所有节点的值都小于根节点的值，右子树的所有节点的值都大于根节点的值。对于给定树中的希腊字母代表的数字值，需要对可能符合条件的值进行阴影处理。

2. Xelha树（Xelha Trees）

2.1 定义和性质

Xelha树是一种特殊的树，具有以下性质：

最小堆性质：每个节点的值都小于或等于其子节点的值。
中序遍历：Xelha树的中序遍历与输入的数字列表顺序相同。

2.2 有效的Xelha树

确定以下给定序列是否为有效的Xelha树。第一个例子已经完成。
画出对应于序列\(8, 3, 9, 1\)的有效Xelha树。

2.3 验证Xelha树的函数

下面的代码定义了一个函数validXelhaTree，用于验证给定的IntTree是否是对应于指定列表的有效Xelha树。

public class TestXelhaTree {
    public static class IntTree {
        public int item;
        public IntTree left, right;
    }

    public static boolean validXelhaTree(IntTree xt, List<Integer> vals) {
        List<Integer> treeValues = new ArrayList<Integer>();
        getTreeValues(xt, treeValues); // 获取树的所有值
        return isAHeap(xt) && treeValues.equals(vals); // 检查是否是堆并且与输入值相等
    }

    private static void getTreeValues(IntTree xt, List<Integer> treeValues) {
        if (xt == null) return;
        getTreeValues(xt.left, treeValues); // 先遍历左子树
        treeValues.add(xt.item); // 加入当前节点值
        getTreeValues(xt.right, treeValues); // 再遍历右子树
    }

    public static boolean isAHeap(IntTree xt) {
        if (xt == null) return true; // 空树是堆
        if (xt.item > getItem(xt.left)) return false; // 左子树的值应大于等于当前节点值
        if (xt.item > getItem(xt.right)) return false; // 右子树的值应大于等于当前节点值
        return isAHeap(xt.left) && isAHeap(xt.right); // 递归检查左、右子树
    }

    private static int getItem(IntTree x) {
        if (x == null) return Integer.MAX_VALUE; // 返回最大值作为空节点的替代
        return x.item; // 返回当前节点的值
    }
}

3. 从遍历重建树（Reconstructing Trees from Traversals）

3.1 重建二叉树的思路

给定两个整数列表，一个表示二叉树的前序遍历，另一个表示中序遍历。可以通过以下步骤重建二叉树：

识别根节点：前序遍历的第一个元素是根节点。
分割中序遍历：在中序遍历中找到根节点的位置，确定左子树和右子树的节点。
构建子树：根据左子树的节点数量，从前序遍历中提取相应的子列表，递归构建左子树和右子树。

3.2 实现方法

public IntTree constructTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) return null; // 基础情况
    int rootValue = preorder[0]; // 获取根节点值
    IntTree root = new IntTree(); // 创建根节点
    root.item = rootValue;

    // 在中序遍历中找到根节点的索引
    int rootIndex = findIndex(inorder, rootValue);

    // 根据中序遍历的索引分割左右子树
    int[] leftInorder = Arrays.copyOfRange(inorder, 0, rootIndex);
    int[] rightInorder = Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length);

    // 提取前序遍历中对应的左、右子树节点
    int[] leftPreorder = Arrays.copyOfRange(preorder, 1, leftInorder.length + 1);
    int[] rightPreorder = Arrays.copyOfRange(preorder, leftInorder.length + 1, preorder.length);

    // 递归构建左、右子树
    root.left = constructTree(leftPreorder, leftInorder);
    root.right = constructTree(rightPreorder, rightInorder);

    return root; // 返回重建的树
}

// 查找根节点在中序遍历中的索引
private int findIndex(int[] inorder, int value) {
    for (int i = 0; i < inorder.length; i++) {
        if (inorder[i] == value) {
            return i;
        }
    }
    return -1; // 未找到则返回-1
}

重建二叉树的题目是LeetCode上的一道经典题目。

题目描述

给定两个整数数组 preorder 和 inorder ，其中：

preorder 是二叉树的前序遍历数组。
inorder 是二叉树的中序遍历数组。

请你构造并返回这棵树的根节点。

示例

示例 1

1 2	输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]

示例 2

1 2	输入: preorder = [-1], inorder = [-1] 输出: [-1]

示例 3

1 2	输入: [], inorder = [] 输出: []

解题思路

前序遍历特点：前序遍历的第一个元素是树的根节点。
中序遍历特点：在中序遍历中，根节点左边的元素是左子树，右边的元素是右子树。
递归构建：
- 从前序数组中取出根节点，找到该根节点在中序数组中的索引。
- 利用该索引划分中序数组为左子树和右子树。
- 根据划分出的左子树和右子树的节点数量，从前序数组中提取对应的节点。
- 递归构建左右子树。