Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. Basically, the deletion can be divided into two stages: Search for a node to remove. If the node is found, delete the node. Note: Time complexity should be O(height of tree). Example: root = [5,3,6,2,4,null,7] key = 3 5 / 3 6 / \ 2 4 7 Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the following BST. 5 / 4 6 / 2 7 Another valid answer is [5,2,6,null,4,null,7]. 5 / 2 6 \ 4 7
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode deleteNode(TreeNode root, int key) { if (root == null) { return null; } if (root.val > key) { root.left = deleteNode(root.left, key); } else if (root.val < key) { root.right = deleteNode(root.right, key); } else if (root.left != null && root.right != null){ TreeNode node = findMax(root.left); root.val = node.val; root.left = deleteNode(root.left, node.val); } else if (root.left != null){ root = root.left; } else { root = root.right; } return root; } public TreeNode findMax(TreeNode root) { while(root != null && root.right != null) { root = root.right; } return root; } }
Reference: https://blog.csdn.net/u013325815/article/details/53146954
LeetCode - Delete Node in a BST
原文:https://www.cnblogs.com/incrediblechangshuo/p/13036854.html