450. 删除二叉搜索树中的节点

题目描述

输入二叉搜索树的根节点 root 和一个整数 key。树用层序数组表示，空位写 null。

若树中有值为 key 的节点，就把它删除，并调整结构使剩下的树依然满足二叉搜索树的性质；若没有，树保持不变。

返回操作后的根节点（根本身也可能被删掉而换成别的节点）。树为空时返回空。删除后的形状可能有多种，只要是合法的二叉搜索树且节点集合正确即可。

示例 1

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]

解释：删除节点 3 后，用它的右子 4 顶替其位置，得到 [5,4,6,2,null,null,7]。

示例 2

输入：root = [5,3,6,2,4,null,7], key = 0
输出：[5,3,6,2,4,null,7]

解释：树中没有值为 0 的节点，原样返回。

示例 3

输入：root = [], key = 0
输出：[]

解释：空树中没有可删的节点，结果仍为空。

数据范围

节点个数在 [0, 10^4] 范围内。
-10^5 <= Node.val <= 10^5
所有节点值互不相同。
root 是合法的二叉搜索树。
-10^5 <= key <= 10^5

进阶：能否让时间复杂度为 O(h)，其中 h 是树高？

解题思路：递归删除

先按 BST 性质递归查找：key 小就去左子树删，大就去右子树删，并把返回的新子树根接回来。找到后分三种情况：没有左孩子就返回右孩子；没有右孩子就返回左孩子；两个孩子都在，就找到右子树中最小的节点（后继），把它的值拷到当前节点，再到右子树里删除后继。

为什么正确

deleteNode(node, key) 返回的是从以 node 为根的 BST 中删去 key 后的新根，子树其余元素不变且仍满足 BST 性质。

复杂度分析

时间 O(h)，空间 O(h)，h 为树高。

易错点

一定要把递归返回值重新赋给 root.left 或 root.right，否则删除只在局部变量上生效。删除根节点时返回的新根可能是另一个节点。改写为后继值后，要删的是右子树中的后继值，而不是原来的 key。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            succ = root.right
            while succ.left:
                succ = succ.left
            root.val = succ.val
            root.right = self.deleteNode(root.right, succ.val)
        return root

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            TreeNode succ = root.right;
            while (succ.left != null) {
                succ = succ.left;
            }
            root.val = succ.val;
            root.right = deleteNode(root.right, succ.val);
        }
        return root;
    }
}

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) {
            return nullptr;
        }
        if (key < root->val) {
            root->left = deleteNode(root->left, key);
        } else if (key > root->val) {
            root->right = deleteNode(root->right, key);
        } else {
            if (!root->left) {
                return root->right;
            }
            if (!root->right) {
                return root->left;
            }
            TreeNode* succ = root->right;
            while (succ->left) {
                succ = succ->left;
            }
            root->val = succ->val;
            root->right = deleteNode(root->right, succ->val);
        }
        return root;
    }
};

func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return nil
	}
	if key < root.Val {
		root.Left = deleteNode(root.Left, key)
	} else if key > root.Val {
		root.Right = deleteNode(root.Right, key)
	} else {
		if root.Left == nil {
			return root.Right
		}
		if root.Right == nil {
			return root.Left
		}
		succ := root.Right
		for succ.Left != nil {
			succ = succ.Left
		}
		root.Val = succ.Val
		root.Right = deleteNode(root.Right, succ.Val)
	}
	return root
}

var deleteNode = function(root, key) {
    if (!root) {
        return null;
    }
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        if (!root.left) {
            return root.right;
        }
        if (!root.right) {
            return root.left;
        }
        let succ = root.right;
        while (succ.left) {
            succ = succ.left;
        }
        root.val = succ.val;
        root.right = deleteNode(root.right, succ.val);
    }
    return root;
};

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
    if (!root) {
        return null;
    }
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        if (!root.left) {
            return root.right;
        }
        if (!root.right) {
            return root.left;
        }
        let succ: TreeNode = root.right;
        while (succ.left) {
            succ = succ.left;
        }
        root.val = succ.val;
        root.right = deleteNode(root.right, succ.val);
    }
    return root;
}

载入编辑器，自己跑一遍 →

其他解法

递归写法把“删除后返回新子树根”交给返回值，简洁；迭代写法省掉递归栈，但要手动维护父指针。

解法 2：迭代删除时间 O(h)，空间 O(1)

先沿 BST 迭代找到目标节点 cur 和它的父节点。若 cur 有两个孩子，找右子树最左的后继节点，把后继的值写入 cur，转为删除后继（后继没有左孩子）。此时要删的节点至多一个孩子，让父节点直接指向这个孩子即可；没有父节点时返回孩子作为新根。

只用常数额外空间，没有递归栈。需要手动记录父节点并判断是左孩子还是右孩子，分支较多。

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        # 1. 迭代查找目标节点及其父节点
        parent, cur = None, root
        while cur and cur.val != key:
            parent = cur
            cur = cur.left if key < cur.val else cur.right
        if not cur:
            return root
        # 2. 有两个孩子：用后继的值覆盖，再改为删除后继（后继没有左孩子）
        if cur.left and cur.right:
            sp, succ = cur, cur.right
            while succ.left:
                sp, succ = succ, succ.left
            cur.val = succ.val
            parent, cur = sp, succ
        # 3. 现在 cur 至多一个孩子，用孩子顶替它
        child = cur.left if cur.left else cur.right
        if not parent:
            return child
        if parent.left is cur:
            parent.left = child
        else:
            parent.right = child
        return root

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode parent = null, cur = root;
        while (cur != null && cur.val != key) {
            parent = cur;
            cur = key < cur.val ? cur.left : cur.right;
        }
        if (cur == null) return root;
        if (cur.left != null && cur.right != null) {
            TreeNode sp = cur, succ = cur.right;
            while (succ.left != null) {
                sp = succ;
                succ = succ.left;
            }
            cur.val = succ.val;
            parent = sp;
            cur = succ;
        }
        TreeNode child = cur.left != null ? cur.left : cur.right;
        if (parent == null) return child;
        if (parent.left == cur) parent.left = child;
        else parent.right = child;
        return root;
    }
}

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        TreeNode* parent = nullptr;
        TreeNode* cur = root;
        while (cur && cur->val != key) {
            parent = cur;
            cur = key < cur->val ? cur->left : cur->right;
        }
        if (!cur) return root;
        if (cur->left && cur->right) {
            TreeNode* sp = cur;
            TreeNode* succ = cur->right;
            while (succ->left) {
                sp = succ;
                succ = succ->left;
            }
            cur->val = succ->val;
            parent = sp;
            cur = succ;
        }
        TreeNode* child = cur->left ? cur->left : cur->right;
        if (!parent) return child;
        if (parent->left == cur) parent->left = child;
        else parent->right = child;
        return root;
    }
};

func deleteNode(root *TreeNode, key int) *TreeNode {
	var parent *TreeNode
	cur := root
	for cur != nil && cur.Val != key {
		parent = cur
		if key < cur.Val {
			cur = cur.Left
		} else {
			cur = cur.Right
		}
	}
	if cur == nil {
		return root
	}
	if cur.Left != nil && cur.Right != nil {
		sp, succ := cur, cur.Right
		for succ.Left != nil {
			sp, succ = succ, succ.Left
		}
		cur.Val = succ.Val
		parent, cur = sp, succ
	}
	child := cur.Left
	if child == nil {
		child = cur.Right
	}
	if parent == nil {
		return child
	}
	if parent.Left == cur {
		parent.Left = child
	} else {
		parent.Right = child
	}
	return root
}

var deleteNode = function(root, key) {
    let parent = null, cur = root;
    while (cur && cur.val !== key) {
        parent = cur;
        cur = key < cur.val ? cur.left : cur.right;
    }
    if (!cur) return root;
    if (cur.left && cur.right) {
        let sp = cur, succ = cur.right;
        while (succ.left) {
            sp = succ;
            succ = succ.left;
        }
        cur.val = succ.val;
        parent = sp;
        cur = succ;
    }
    const child = cur.left ? cur.left : cur.right;
    if (!parent) return child;
    if (parent.left === cur) parent.left = child;
    else parent.right = child;
    return root;
};

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
    let parent: TreeNode | null = null, cur: TreeNode | null = root;
    while (cur && cur.val !== key) {
        parent = cur;
        cur = key < cur.val ? cur.left : cur.right;
    }
    if (!cur) return root;
    if (cur.left && cur.right) {
        let sp: TreeNode = cur, succ: TreeNode = cur.right;
        while (succ.left) {
            sp = succ;
            succ = succ.left;
        }
        cur.val = succ.val;
        parent = sp;
        cur = succ;
    }
    const child = cur.left ? cur.left : cur.right;
    if (!parent) return child;
    if (parent.left === cur) parent.left = child;
    else parent.right = child;
    return root;
}

二叉树专题的其他题目

查看二叉树全部题目 →