leetcode450. Delete Node in a BST

yzd 發布于2019-08-16 17:33 / 1573人閱讀

摘要：題目要求假設有一棵二叉搜索樹，現在要求從二叉搜索樹中刪除指定值，使得刪除后的結果依然是一棵二叉搜索樹。思路和代碼二叉搜索樹的特點是，對于樹中的任何一個節點，一定滿足大于其所有左子節點值，小于所有其右子節點值。

題目要求

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

假設有一棵二叉搜索樹，現在要求從二叉搜索樹中刪除指定值，使得刪除后的結果依然是一棵二叉搜索樹。

思路和代碼

二叉搜索樹的特點是，對于樹中的任何一個節點，一定滿足大于其所有左子節點值，小于所有其右子節點值。當刪除二叉搜索樹中的一個節點時，一共有三種場景：

該該節點為葉節點，此時無需進行任何操作，直接刪除該節點即可

該節點只有一個子樹，則將唯一的直接子節點替換掉當前的節點即可

該節點既有做左子節點又有右子節點。這時候有兩種選擇，要么選擇左子樹的最大值，要么選擇右子樹的最小值填充至當前的節點，再遞歸的在子樹中刪除對應的最大值或是最小值。

對每種情況的圖例如下：

1. 葉節點
    5
   / 
  2   6
      
    4   7 （刪除4）
結果為：
    5
   / 
  2   6
       
        7
        
2. 只有左子樹或是只有右子樹
    5
   / 
  3   6
 /    
2   4   7（刪除6）
結果為
    5
   / 
  3   6
 /    
2   4   

3. 既有左子樹又有右子樹
    6
   / 
  3   7
 /    
2   5   8 （刪除6）
   /
  4
首先找到6的左子樹中的最大值為5，將5填充到6的位置
    5
   / 
  3   7
 /    
2   5   8 （刪除5）
   /
  4
接著遞歸的在左子樹中刪除5，此時5滿足只有一個子樹的場景，因此直接用子樹替換即可
    5
   / 
  3   7
 /    
2   4   8 （刪除5）

代碼如下：

    public TreeNode deleteNode(TreeNode cur, int key) {
        if(cur == null) return null;
        else if(cur.val == key) {
            if(cur.left != null && cur.right != null) {
                TreeNode left = cur.left;
                while(left.right != null) {
                    left = left.right;
                }
                cur.val = left.val;
                cur.left = deleteNode(cur.left, left.val);
            }else if(cur.left != null) {
                return cur.left;
            }else if(cur.right != null){
                return cur.right;
            }else {
                return null;
            }
        }else if(cur.val > key) {
            cur.left = deleteNode(cur.left, key);
        }else {
            cur.right = deleteNode(cur.right, key);
        }
        return cur;
    }

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/74579.html

[LeetCode] 450. Delete Node in a BST

Problem 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 divi...

spacewander 2019-08-16 13:36 評論0 收藏0
leetcode 315 Count of Smaller Numbers After Self 以

摘要：題目意思就是要一個個的返回當前的最小值。所以解法自然就是。我們需要找出被打亂的點并返回正確結果。然后將兩個不正確的點記錄下來，最后回原來正確的值。如果是葉子節點，或者只有一個子樹。思想來自于的代碼實現。跳過總結請點這里：https://segmentfault.com/a/11... BST最明顯的特點就是root.left.val < root.val < root.right.v...

inapt 2019-08-14 17:20 評論0 收藏0
[Leetcode-Tree]Delete Node in a BST

摘要：解題思路我們可以用遞歸來查找，在找到需要刪除的節點后，我們需要分情況討論節點是葉子節點，直接返回節點有一個孩子，直接返回孩子節點有兩個孩子，我們要將右子樹中最小的節點值賦值給根節點，并在右子樹中刪除掉那個最小的節點。 Delete Node in a BSTGiven a root node reference of a BST and a key, delete the node w...

wangjuntytl 2019-08-16 10:26 評論0 收藏0
[Leetcode-Tree] Kth Smallest Element in a BST

摘要：解題思路本題需要找的是第小的節點值，而二叉搜索樹的中序遍歷正好是數值從小到大排序的，那么這題就和中序遍歷一個情況。 Kth Smallest Element in a BSTGiven a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You ...

Carl 2019-08-16 10:26 評論0 收藏0
[Leetcode] Kth Smallest Element in a BST 二叉搜索樹第k小節

摘要：中序遍歷復雜度時間空間思路因為左節點小于根節點小于右節點，二叉搜索樹的一個特性就是中序遍歷的結果就是樹內節點從小到大順序輸出的結果。這里采用迭代形式，我們就可以在找到第小節點時馬上退出。這樣我們就可以用二叉樹搜索的方法來解決這個問題了。 Kth Smallest Element in a BST Given a binary search tree, write a function...

Dean 2019-08-14 12:26 評論0 收藏0