本文共 2135 字，大约阅读时间需要 7 分钟。

问题一：二叉搜索树的最近公共祖先

方法一：迭代法

代码示例：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (p.val > q.val) {
        TreeNode tmp = p;
        p = q;
        q = tmp;
    }
    while (root != null) {
        if (root.val < p.val) {
            root = root.right;
        } else if (root.val > q.val) {
            root = root.left;
        } else {
            break;
        }
    }
    return root;
}

方法二：递归法

代码示例：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (p.val > q.val) {
        TreeNode tmp = p;
        p = q;
        q = tmp;
    }
    return helper(root, p, q);
}
private TreeNode helper(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return null;
    }
    if (root.val < p.val) {
        return helper(root.right, p, q);
    } else if (root.val > q.val) {
        return helper(root.left, p, q);
    } else {
        return root;
    }
}

问题二：重建二叉树

方法：分治法

代码示例：

public TreeNode buildTree(int[] preorder, int[] inorder) {
    HashMap
   
     map = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        map.put(inorder[i], i);
    }
    return build(0, 0, inorder.length - 1);
}
private TreeNode build(int rootIndex, int left, int right) {
    if (left > right) {
        return null;
    }
    int currentVal = preorder[rootIndex];
    int rootInOrderIndex = map.get(currentVal);
    TreeNode node = new TreeNode(currentVal);
    // 构建左子树
    node.left = build(rootIndex + 1, left, rootInOrderIndex - 1);
    // 构建右子树
    int rightStart = rootInOrderIndex + 1;
    int rightEnd = right;
    node.right = build(rootIndex + rightStart - left, rightStart, rightEnd);
    return node;
}
   

总结

通过以上方法，可以高效地解决二叉搜索树的最近公共祖先问题和二叉树的重建问题。迭代法和递归法各有优劣，选择时需根据具体需求权衡。重建二叉树的分治法利用了前序和中序遍历的特性，确保了构建的准确性和效率。