Skip to content

Latest commit

 

History

History
663 lines (582 loc) · 21.7 KB

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

File metadata and controls

663 lines (582 loc) · 21.7 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

二叉搜索树删除节点就涉及到结构调整了

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

力扣题目链接

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点； 如果找到了，删除它。 说明： 要求算法时间复杂度为 $O(h)$，h 为树的高度。

示例:

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

思路

搜索树的节点删除要比节点增加复杂的多，有很多情况需要考虑，做好心里准备。

递归

递归三部曲：

  • 确定递归函数参数以及返回值

说道递归函数的返回值，在二叉树：搜索树中的插入操作中通过递归返回值来加入新节点， 这里也可以通过递归返回值删除节点。

代码如下：

TreeNode* deleteNode(TreeNode* root, int key)
  • 确定终止条件

遇到空返回，其实这也说明没找到删除的节点，遍历到空节点直接返回了

if (root == nullptr) return root;
  • 确定单层递归的逻辑

这里就把二叉搜索树中删除节点遇到的情况都搞清楚。

有以下五种情况：

  • 第一种情况：没找到删除的节点，遍历到空节点直接返回了
  • 找到删除的节点
    • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
    • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
    • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
    • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

第五种情况有点难以理解，看下面动画：

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

动画中棵二叉搜索树中，删除元素7， 那么删除节点（元素7）的左孩子就是5，删除节点（元素7）的右子树的最左面节点是元素8。

将删除节点（元素7）的左孩子放到删除节点（元素7）的右子树的最左面节点（元素8）的左孩子上，就是把5为根节点的子树移到了8的左孩子的位置。

要删除的节点（元素7）的右孩子（元素9）为新的根节点。.

这样就完成删除元素7的逻辑，最好动手画一个图，尝试删除一个节点试试。

代码如下：

if (root->val == key) {
    // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
    // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
    if (root->left == nullptr) return root->right;
    // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
    else if (root->right == nullptr) return root->left;
    // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
    // 并返回删除节点右孩子为新的根节点。
    else {
        TreeNode* cur = root->right; // 找右子树最左面的节点
        while(cur->left != nullptr) {
            cur = cur->left;
        }
        cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
        TreeNode* tmp = root;   // 把root节点保存一下，下面来删除
        root = root->right;     // 返回旧root的右孩子作为新root
        delete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
        return root;
    }
}

这里相当于把新的节点返回给上一层，上一层就要用 root->left 或者 root->right接住，代码如下：

if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;

整体代码如下：（注释中：情况1，2，3，4，5和上面分析严格对应）

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
        if (root->val == key) {
            // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
            if (root->left == nullptr && root->right == nullptr) {
                ///! 内存释放
                delete root;
                return nullptr;
            }
            // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
            else if (root->left == nullptr) {
                auto retNode = root->right;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
            else if (root->right == nullptr) {
                auto retNode = root->left;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
            // 并返回删除节点右孩子为新的根节点。
            else {
                TreeNode* cur = root->right; // 找右子树最左面的节点
                while(cur->left != nullptr) {
                    cur = cur->left;
                }
                cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
                TreeNode* tmp = root;   // 把root节点保存一下，下面来删除
                root = root->right;     // 返回旧root的右孩子作为新root
                delete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
                return root;
            }
        }
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key) root->right = deleteNode(root->right, key);
        return root;
    }
};

普通二叉树的删除方式

这里我在介绍一种通用的删除，普通二叉树的删除方式（没有使用搜索树的特性，遍历整棵树），用交换值的操作来删除目标节点。

代码中目标节点（要删除的节点）被操作了两次：

  • 第一次是和目标节点的右子树最左面节点交换。
  • 第二次直接被NULL覆盖了。

思路有点绕，感兴趣的同学可以画图自己理解一下。

代码如下：（关键部分已经注释）

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root;
        if (root->val == key) {
            if (root->right == nullptr) { // 这里第二次操作目标值：最终删除的作用
                return root->left;
            }
            TreeNode *cur = root->right;
            while (cur->left) {
                cur = cur->left;
            }
            swap(root->val, cur->val); // 这里第一次操作目标值：交换目标值其右子树最左面节点。
        }
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }
};

这个代码是简短一些，思路也巧妙，但是不太好想，实操性不强，推荐第一种写法！

迭代法

删除节点的迭代法还是复杂一些的，但其本质我在递归法里都介绍了，最关键就是删除节点的操作（动画模拟的过程）

代码如下：

class Solution {
private:
    // 将目标节点（删除节点）的左子树放到 目标节点的右子树的最左面节点的左孩子位置上
    // 并返回目标节点右孩子为新的根节点
    // 是动画里模拟的过程
    TreeNode* deleteOneNode(TreeNode* target) {
        if (target == nullptr) return target;
        if (target->right == nullptr) return target->left;
        TreeNode* cur = target->right;
        while (cur->left) {
            cur = cur->left;
        }
        cur->left = target->left;
        return target->right;
    }
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root;
        TreeNode* cur = root;
        TreeNode* pre = nullptr; // 记录cur的父节点，用来删除cur
        while (cur) {
            if (cur->val == key) break;
            pre = cur;
            if (cur->val > key) cur = cur->left;
            else cur = cur->right;
        }
        if (pre == nullptr) { // 如果搜索树只有头结点
            return deleteOneNode(cur);
        }
        // pre 要知道是删左孩子还是右孩子
        if (pre->left && pre->left->val == key) {
            pre->left = deleteOneNode(cur);
        }
        if (pre->right && pre->right->val == key) {
            pre->right = deleteOneNode(cur);
        }
        return root;
    }
};

总结

读完本篇，大家会发现二叉搜索树删除节点比增加节点复杂的多。

因为二叉搜索树添加节点只需要在叶子上添加就可以的，不涉及到结构的调整，而删除节点操作涉及到结构的调整。

这里我们依然使用递归函数的返回值来完成把节点从二叉树中移除的操作。

这里最关键的逻辑就是第五种情况（删除一个左右孩子都不为空的节点），这种情况一定要想清楚。

而且就算想清楚了，对应的代码也未必可以写出来，所以这道题目即考察思维逻辑，也考察代码能力。

递归中我给出了两种写法，推荐大家学会第一种（利用搜索树的特性）就可以了，第二种递归写法其实是比较绕的。

最后我也给出了相应的迭代法，就是模拟递归法中的逻辑来删除节点，但需要一个pre记录cur的父节点，方便做删除操作。

迭代法其实不太容易写出来，所以如果是初学者的话，彻底掌握第一种递归写法就够了。

其他语言版本

Java

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        root = delete(root,key);
        return root;
    }

    private TreeNode delete(TreeNode root, int key) {
        if (root == null) return null;

        if (root.val > key) {
            root.left = delete(root.left,key);
        } else if (root.val < key) {
            root.right = delete(root.right,key);
        } else {
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            TreeNode tmp = root.right;
            while (tmp.left != null) {
                tmp = tmp.left;
            }
            root.val = tmp.val;
            root.right = delete(root.right,tmp.val);
        }
        return root;
    }
}
// 解法2
class Solution {
  public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return root;
    if (root.val == key) {
      if (root.left == null) {
        return root.right;
      } else if (root.right == null) {
        return root.left;
      } else {
        TreeNode cur = root.right;
        while (cur.left != null) {
          cur = cur.left;
        }
        cur.left = root.left;
        root = root.right;
        return root;
      }
    }
    if (root.val > key) root.left = deleteNode(root.left, key);
    if (root.val < key) root.right = deleteNode(root.right, key);
    return root;
  }
}

Python

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root : return  None # 节点为空，返回
        if root.val < key :
            root.right = self.deleteNode(root.right, key)
        elif root.val > key :
            root.left = self.deleteNode(root.left, key)
        else:
            # 当前节点的左子树为空，返回当前的右子树
            if not root.left : return root.right
            # 当前节点的右子树为空，返回当前的左子树
            if not root.right: return root.left
            # 左右子树都不为空，找到右孩子的最左节点 记为p
            node = root.right
            while node.left :
                node = node.left
            # 将当前节点的左子树挂在p的左孩子上
            node.left = root.left
            # 当前节点的右子树替换掉当前节点，完成当前节点的删除
            root = root.right
        return root

迭代法

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        # 找到节点后分两步，1. 把节点的左子树和右子树连起来，2. 把右子树跟父节点连起来
        # root is None
        if not root: return root
        p = root
        last = None
        while p:
            if p.val==key:
                # 1. connect left to right
                # right is not None -> left is None | left is not None
                if p.right:
                    if p.left:
                        node = p.right
                        while node.left:
                            node = node.left
                        node.left = p.left
                    right = p.right
                else:
                # right is None -> right=left
                    right = p.left
                # 2. connect right to last
                if last==None:
                    root = right
                elif last.val>key:
                    last.left = right
                else:
                    last.right = right
                # 3. return
                break
            else:
                # Update last and continue
                last = p
                if p.val>key:
                    p = p.left
                else:
                    p = p.right
        return root

Go

// 递归版本
func deleteNode(root *TreeNode, key int) *TreeNode {
    if root==nil{
        return nil
    }
    if key<root.Val{
        root.Left=deleteNode(root.Left,key)
        return root
    }
    if key>root.Val{
        root.Right=deleteNode(root.Right,key)
        return root
    }
    if root.Right==nil{
        return root.Left
    }
    if root.Left==nil{
        return root.Right
    }
    minnode:=root.Right
    for minnode.Left!=nil{
        minnode=minnode.Left
    }
    root.Val=minnode.Val
    root.Right=deleteNode1(root.Right)
    return root
}

func deleteNode1(root *TreeNode)*TreeNode{
    if root.Left==nil{
        pRight:=root.Right
        root.Right=nil
        return pRight
    }
    root.Left=deleteNode1(root.Left)
    return root
}
// 迭代版本
func deleteOneNode(target *TreeNode) *TreeNode {
	if target == nil {
		return target
	}
	if target.Right == nil {
		return target.Left
	}
	cur := target.Right
	for cur.Left != nil {
		cur = cur.Left
	}
	cur.Left = target.Left
	return target.Right
}
func deleteNode(root *TreeNode, key int) *TreeNode {
	// 特殊情况处理
	if root == nil {
		return root
	}
	cur := root
	var pre *TreeNode
	for cur != nil {
		if cur.Val == key {
			break
		}
		pre = cur
		if cur.Val > key {
			cur = cur.Left
		} else {
			cur = cur.Right
		}
	}
	if pre == nil {
		return deleteOneNode(cur)
	}
	// pre 要知道是删除左孩子还有右孩子
	if pre.Left != nil && pre.Left.Val == key {
		pre.Left = deleteOneNode(cur)
	}
	if pre.Right != nil && pre.Right.Val == key {
		pre.Right = deleteOneNode(cur)
	}
	return root
}

JavaScript

递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function(root, key) {
    if (!root) return null;
    if (key > root.val) {
        root.right = deleteNode(root.right, key);
        return root;
    } else if (key < root.val) {
        root.left = deleteNode(root.left, key);
        return root;
    } else {
        // 场景1: 该节点是叶节点
        if (!root.left && !root.right) {
            return null
        }
        // 场景2: 有一个孩子节点不存在
        if (root.left && !root.right) {
            return root.left;
        } else if (root.right && !root.left) {
            return root.right;
        }
        // 场景3: 左右节点都存在
        const rightNode = root.right;
        // 获取最小值节点
        const minNode = getMinNode(rightNode);
        // 将待删除节点的值替换为最小值节点值
        root.val = minNode.val;
        // 删除最小值节点
        root.right = deleteNode(root.right, minNode.val);
        return root;
    }
};
function getMinNode(root) {
    while (root.left) {
        root = root.left;
    }
    return root;
}

迭代

var deleteNode = function (root, key) {
    const deleteOneNode = target => {
        if (!target) return target
        if (!target.right) return target.left
        let cur = target.right
        while (cur.left) {
            cur = cur.left
        }
        cur.left = target.left
        return target.right
    }

    if (!root) return root
    let cur = root
    let pre = null
    while (cur) {
        if (cur.val === key) break
        pre = cur
        cur.val > key ? cur = cur.left : cur = cur.right
    }
    if (!pre) {
        return deleteOneNode(cur)
    }
    if (pre.left && pre.left.val === key) {
        pre.left = deleteOneNode(cur)
    }
    if (pre.right && pre.right.val === key) {
        pre.right = deleteOneNode(cur)
    }
    return root
}

TypeScript

递归法：

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

迭代法：

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
    function removeTargetNode(root: TreeNode): TreeNode | null {
        if (root.left === null && root.right === null) return null;
        if (root.right === null) return root.left;
        if (root.left === null) return root.right;
        let curNode: TreeNode | null = root.right;
        while (curNode.left !== null) {
            curNode = curNode.left;
        }
        curNode.left = root.left;
        return root.right;
    }
    let preNode: TreeNode | null = null,
        curNode: TreeNode | null = root;
    while (curNode !== null) {
        if (curNode.val === key) break;
        preNode = curNode;
        if (curNode.val > key) {
            curNode = curNode.left;
        } else {
            curNode = curNode.right;
        }
    }
    if (curNode === null) return root;
    if (preNode === null) {
        // 删除头节点
        return removeTargetNode(curNode);
    }
    if (preNode.val > key) {
        preNode.left = removeTargetNode(curNode);
    } else {
        preNode.right = removeTargetNode(curNode);
    }
    return root;
};

Scala

object Solution {
  def deleteNode(root: TreeNode, key: Int): TreeNode = {
    if (root == null) return root // 第一种情况，没找到删除的节点，遍历到空节点直接返回
    if (root.value == key) {
      // 第二种情况: 左右孩子都为空，直接删除节点，返回null
      if (root.left == null && root.right == null) return null
      // 第三种情况: 左孩子为空，右孩子不为空，右孩子补位
      else if (root.left == null && root.right != null) return root.right
      // 第四种情况: 左孩子不为空，右孩子为空，左孩子补位
      else if (root.left != null && root.right == null) return root.left
      // 第五种情况: 左右孩子都不为空，将删除节点的左子树头节点(左孩子)放到
      //           右子树的最左边节点的左孩子上，返回删除节点的右孩子
      else {
        var tmp = root.right
        while (tmp.left != null) tmp = tmp.left
        tmp.left = root.left
        return root.right
      }
    }
    if (root.value > key) root.left = deleteNode(root.left, key)
    if (root.value < key) root.right = deleteNode(root.right, key)

    root // 返回根节点，return关键字可以省略
  }
}