国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專(zhuān)欄INFORMATION COLUMN

[Leetcode-Tree]Delete Node in a BST

wangjuntytl / 1415人閱讀

摘要：解題思路我們可以用遞歸來(lái)查找，在找到需要?jiǎng)h除的節(jié)點(diǎn)后，我們需要分情況討論節(jié)點(diǎn)是葉子節(jié)點(diǎn)，直接返回節(jié)點(diǎn)有一個(gè)孩子，直接返回孩子節(jié)點(diǎn)有兩個(gè)孩子，我們要將右子樹(shù)中最小的節(jié)點(diǎn)值賦值給根節(jié)點(diǎn)，并在右子樹(shù)中刪除掉那個(gè)最小的節(jié)點(diǎn)。

Delete Node in a BST
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

解題思路

我們可以用遞歸來(lái)查找Key，在找到需要?jiǎng)h除的節(jié)點(diǎn)后，我們需要分情況討論：
1） 節(jié)點(diǎn)是葉子節(jié)點(diǎn)，直接返回null;
2) 節(jié)點(diǎn)有一個(gè)孩子，直接返回孩子；
3）節(jié)點(diǎn)有兩個(gè)孩子，我們要將右子樹(shù)中最小的節(jié)點(diǎn)值賦值給根節(jié)點(diǎn)，并在右子樹(shù)中刪除掉那個(gè)最小的節(jié)點(diǎn)。

2.代碼

public class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null) return root;
        if(key>root.val)
            root.right=deleteNode(root.right,key);
        else if(key

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/69808.html

相關(guān)文章

  • [Leetcode-Tree] Kth Smallest Element in a BST

    摘要：解題思路本題需要找的是第小的節(jié)點(diǎn)值，而二叉搜索樹(shù)的中序遍歷正好是數(shù)值從小到大排序的，那么這題就和中序遍歷一個(gè)情況。 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 評(píng)論0 收藏0

  • [Leetcode-Tree] Convert Sorted Array to Binary Sea

    摘要：解題思路平衡二叉樹(shù)，其實(shí)就是數(shù)組中間的數(shù)作為根，利用遞歸實(shí)現(xiàn)左子樹(shù)和右子樹(shù)的構(gòu)造。 Convert Sorted Array to Binary Search TreeGiven an array where elements are sorted in ascending order, convert it to a height balanced BST. 1.解題思路平衡二叉樹(shù)，...

    songze 評(píng)論0 收藏0

  • [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 評(píng)論0 收藏0

  • leetcode450. Delete Node in a BST

    摘要：題目要求假設(shè)有一棵二叉搜索樹(shù)，現(xiàn)在要求從二叉搜索樹(shù)中刪除指定值，使得刪除后的結(jié)果依然是一棵二叉搜索樹(shù)。思路和代碼二叉搜索樹(shù)的特點(diǎn)是，對(duì)于樹(shù)中的任何一個(gè)節(jié)點(diǎn)，一定滿足大于其所有左子節(jié)點(diǎn)值，小于所有其右子節(jié)點(diǎn)值。 題目要求 Given a root node reference of a BST and a key, delete the node with the given key i...

    yzd 評(píng)論0 收藏0

  • [Leetcode-Tree]Sum of Left Leaves

    摘要：解題思路這個(gè)題目其實(shí)就是基于先序遍歷，用遞歸和非遞歸思想都可以。遞歸求所有左葉子節(jié)點(diǎn)的和，我們可以將其分解為左子樹(shù)的左葉子和右子樹(shù)的左葉子和遞歸結(jié)束條件找到左葉子節(jié)點(diǎn)，就可以返回該節(jié)點(diǎn)的。代碼非遞歸判斷是否為左葉子節(jié)點(diǎn)遞歸 Sum of Left LeavesFind the sum of all left leaves in a given binary tree. Example:...

    ashe 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<