树的构造与序列化（前序+中序 · 后序+中序 · 序列化）

由前序+中序序列构造二叉树（LeetCode 105）

思路：前序第一个是根，在中序中找根的位置，划分左右子树。

Map<Integer, Integer> inorderIdx;

TreeNode buildTree(int[] preorder, int[] inorder) {
    inorderIdx = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) inorderIdx.put(inorder[i], i);
    return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
}

TreeNode build(int[] pre, int pl, int pr, int il, int ir) {
    if (pl > pr) return null;
    int rootVal = pre[pl];
    int i = inorderIdx.get(rootVal);
    int leftSize = i - il;
    TreeNode root = new TreeNode(rootVal);
    root.left  = build(pre, pl + 1, pl + leftSize, il, i - 1);
    root.right = build(pre, pl + leftSize + 1, pr, i + 1, ir);
    return root;
}

由后序+中序序列构造二叉树（LeetCode 106）

后序最后一个是根，其余同上：

TreeNode build(int[] post, int pl, int pr, int il, int ir) {
    if (pl > pr) return null;
    int rootVal = post[pr];  // 后序最后 = 根
    int i = inorderIdx.get(rootVal);
    int leftSize = i - il;
    TreeNode root = new TreeNode(rootVal);
    root.left  = build(post, pl, pl + leftSize - 1, il, i - 1);
    root.right = build(post, pl + leftSize, pr - 1, i + 1, ir);
    return root;
}

序列化与反序列化（LeetCode 297）

前序 DFS

// 序列化
String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    dfs(root, sb);
    return sb.toString();
}
void dfs(TreeNode node, StringBuilder sb) {
    if (node == null) { sb.append("null,"); return; }
    sb.append(node.val).append(',');
    dfs(node.left, sb);
    dfs(node.right, sb);
}

// 反序列化
int idx = 0;
TreeNode deserialize(String data) {
    String[] arr = data.split(",");
    return rebuild(arr);
}
TreeNode rebuild(String[] arr) {
    if ("null".equals(arr[idx])) { idx++; return null; }
    TreeNode node = new TreeNode(Integer.parseInt(arr[idx++]));
    node.left  = rebuild(arr);
    node.right = rebuild(arr);
    return node;
}

从前序遍历重建二叉树（LeetCode 1008，BST）

TreeNode bstFromPreorder(int[] preorder) {
    return build(preorder, 0, preorder.length - 1);
}
TreeNode build(int[] pre, int left, int right) {
    if (left > right) return null;
    TreeNode root = new TreeNode(pre[left]);
    // 找第一个大于根的位置
    int i = left + 1;
    while (i <= right && pre[i] < pre[left]) i++;
    root.left  = build(pre, left + 1, i - 1);
    root.right = build(pre, i, right);
    return root;
}

最近公共祖先（LCA，LeetCode 236）

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left  = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // 两侧都找到，当前节点就是LCA
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

BST 的 LCA（LeetCode 235）

TreeNode lcaBST(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) root = root.left;
        else if (p.val > root.val && q.val > root.val) root = root.right;
        else return root;
    }
    return null;
}