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

450. 删除二叉搜索树中的节点 给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
【LeetCode|450. 删除二叉搜索树中的节点】一般来说,删除节点可分为两个步骤:

  1. 首先找到需要删除的节点;
  2. 如果找到了,删除它。
示例 1:
LeetCode|450. 删除二叉搜索树中的节点
文章图片

输入:root = [5,3,6,2,4,null,7], key = 3
输出:[5,4,6,2,null,null,7]
解释:给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。
LeetCode|450. 删除二叉搜索树中的节点
文章图片

示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点
示例 3:
输入: root = [], key = 0
输出: []
思考 我们删除一个节点,首先考虑特殊情况
  • 该树为空,直接返回null
  • 该节点为树的根节点,并且没有左右子树,返回null
前序遍历函数
  • 处理
  • 遍历左子树
  • 遍历右子树
定义前序遍历递归,其参数
  • pre代表访问该节点的父节点,初始化为null
  • root代表正在访问的节点
  • key
其递归需要返回值 ,因为会出现两种情况
  • 如果删除的节点不是根节点,preOrder函数返回null,deleteNode返回root
  • 如果删除的节点是根节点,preOrder函数返回新的根tempRoot,deleteNode返回tempRoot
前序遍历函数处理过程:
  • 如果该节点的值等于key,说明需要删除此节点
LeetCode|450. 删除二叉搜索树中的节点
文章图片

此图代表left和right非空时
  • root代表需要删除的节点
  • left代表root的左孩子(可能为null)
  • right代表root的右孩子(可能为null)
  • pre代表root的父节点,但是我们不知道root是pre的左孩子还是右孩子
    • 但是由于该树是搜索二叉树,所以我们可以根据pre.val和root.val来判断
  • 我们只需把b(可能为null)移动到c(可能为null)的左子树即可
注意:还有left和right可能为空的情况,这里不在画图赘述,大致相同。
public TreeNode deleteNode(TreeNode root, int key) { if(root==null) return null; if(root.val==key){ if(root.left==null&&root.right==null) return null; } TreeNode temp =null; temp = preOrder(null,root,key); if(temp!=null) return temp; return root; }private TreeNode preOrder(TreeNode pre, TreeNode root, int key) { TreeNode temp = null; if(root.val == key){TreeNode temproot = null; TreeNode left=root.left; TreeNode right=root.right; if(right==null){ temproot = left; }else if(right!=null){ if(left==null){ temproot=right; }else{ TreeNode righttemp = right; while (righttemp.left!=null){ righttemp = righttemp.left; } righttemp.left=left.right; left.right=right; temproot =left; } } if(pre==null){ return temproot; } if(pre!=null){ if(pre.val>root.val){ pre.left= temproot; } if(pre.val

    推荐阅读