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 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 7Solution
class Solution { public TreeNode deleteNode(TreeNode root, int key) { if (root == null) return root; if (root.val < key) root.right = deleteNode(root.right, key); else if (root.val > key) root.left = deleteNode(root.left, key); else { if (root.left == null) return root.right; if (root.right == null) return root.left; int min = findMin(root.right); root.val = min; root.right = deleteNode(root.right, min); } return root; } private int findMin(TreeNode node) { while (node.left != null) node = node.left; return node.val; } }
文章版權歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/72000.html
摘要:題目要求假設有一棵二叉搜索樹,現(xiàn)在要求從二叉搜索樹中刪除指定值,使得刪除后的結果依然是一棵二叉搜索樹。思路和代碼二叉搜索樹的特點是,對于樹中的任何一個節(jié)點,一定滿足大于其所有左子節(jié)點值,小于所有其右子節(jié)點值。 題目要求 Given a root node reference of a BST and a key, delete the node with the given key i...
摘要:題目意思就是要一個個的返回當前的最小值。所以解法自然就是。我們需要找出被打亂的點并返回正確結果。然后將兩個不正確的點記錄下來,最后回原來正確的值。如果是葉子節(jié)點,或者只有一個子樹。思想來自于的代碼實現(xiàn)。 跳過總結請點這里:https://segmentfault.com/a/11... BST最明顯的特點就是root.left.val < root.val < root.right.v...
摘要:解題思路我們可以用遞歸來查找,在找到需要刪除的節(jié)點后,我們需要分情況討論節(jié)點是葉子節(jié)點,直接返回節(jié)點有一個孩子,直接返回孩子節(jié)點有兩個孩子,我們要將右子樹中最小的節(jié)點值賦值給根節(jié)點,并在右子樹中刪除掉那個最小的節(jié)點。 Delete Node in a BSTGiven a root node reference of a BST and a key, delete the node w...
摘要:解題思路本題需要找的是第小的節(jié)點值,而二叉搜索樹的中序遍歷正好是數(shù)值從小到大排序的,那么這題就和中序遍歷一個情況。 Kth Smallest Element in a BSTGiven a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You ...
摘要:中序遍歷復雜度時間空間思路因為左節(jié)點小于根節(jié)點小于右節(jié)點,二叉搜索樹的一個特性就是中序遍歷的結果就是樹內(nèi)節(jié)點從小到大順序輸出的結果。這里采用迭代形式,我們就可以在找到第小節(jié)點時馬上退出。這樣我們就可以用二叉樹搜索的方法來解決這個問題了。 Kth Smallest Element in a BST Given a binary search tree, write a function...
閱讀 3422·2023-04-25 22:44
閱讀 926·2021-11-15 11:37
閱讀 1632·2019-08-30 15:55
閱讀 2639·2019-08-30 15:54
閱讀 1080·2019-08-30 13:45
閱讀 1430·2019-08-29 17:14
閱讀 1853·2019-08-29 13:50
閱讀 3402·2019-08-26 11:39