已知二叉树以二叉链表存储。编写算法：删除树中每个元素值为 x 的结点所对应的整棵子树，并释放相应空间。

[tag_link]

参考答案

主过程按引用接收子树根指针。遇到值为 x 的结点时，后序释放其整棵子树并把该父链接改为空；随后不再进入已释放区域。

伪代码

Destroy(ref T):
    if T == null: return
    Destroy(ref T.left)
    Destroy(ref T.right)
    free(T)
    T = null

RemoveX(ref T, x):
    if T == null: return
    if T.data == x:
        Destroy(ref T)
        return
    RemoveX(ref T.left, x)
    RemoveX(ref T.right, x)

复杂度

每个仍可达结点最多访问或释放一次，时间 O(n)；递归栈空间 O(h)。

边界条件

根值为 x 时整棵树被删除；空树直接返回；若祖先已匹配 x，无需再分别寻找其后代中的 x。

易错点

必须先释放孩子再释放根，并通过引用把父结点的对应孩子指针置空，否则会产生悬空指针或释放后访问。

评分要点

后序 Destroy；命中 x 后删除整棵子树；断开父链接；避免二次访问；说明复杂度。