溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
如何刪除二叉樹中的節點，相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。
算法：
1.后驅算法：
/*遞歸解法：1.找到需要刪除的節點2.刪除的節點只有右子樹或者左子樹，直接將右子樹或者左子樹的根節點當作這個刪除的節點3.刪除的節點左右子樹都存在的情況下，左子樹的最大節點也叫做前驅當作刪除節點，或者將右子樹的最小節點也就稱作后驅當作刪除節點。*/
2.前驅算法：
/*遞歸解法：1.找到需要刪除的節點2.刪除的節點只有右子樹或者左子樹，直接將右子樹或者左子樹的根節點當作這個刪除的節點3.刪除的節點左右子樹都存在的情況下，左子樹的最大節點也叫做前驅當作刪除節點，或者將右子樹的最小節點也就稱作后驅當作刪除節點。*/
題目：
后驅算法：
func deleteNode(root *TreeNode, key int) *TreeNode { if root == nil { return nil } if key < root.Val { root.Left = deleteNode(root.Left,key) return root } if key > root.Val { root.Right = deleteNode(root.Right,key) return root } // 這里通過遞歸已經找到了要刪除的節點,此時因為遞歸的原因還是root這個指針 if root.Right == nil { return root.Left } if root.Left == nil { return root.Right } // 后驅的方法來替換當前節點 min := root.Right for min.Left != nil { min = min.Left } root.Val = min.Val // 替換需要刪除的節點的數值，這里就是復制 root.Right = deleteMin(root.Right) // 這里把右子樹中移動過來的那個最小節點刪除掉 return root}func deleteMin(root *TreeNode) *TreeNode{ // 左子樹不在的話，表示這個節點就是要刪除的最小節點 // 存在兩種情況，一：這個節點就是葉子節點，直接通過賦值為nil, 來當作刪除節點。 // 二：這個節點沒有左子樹，只有右子樹，這樣的話，需要將右子樹替換成該節點 if root.Left == nil { right := root.Right root.Right = nil return right } root.Left = deleteMin(root.Left) // 左子樹一直在的話，就一直通過左子樹去找最小節點 return root}
前驅算法
func deleteNode(root *TreeNode, key int) *TreeNode {if root == nil {return nil}if key < root.Val {root.Left = deleteNode(root.Left,key)return root}if key > root.Val {root.Right = deleteNode(root.Right,key)return root}// 這里通過遞歸已經找到了要刪除的節點,此時因為遞歸的原因還是root這個指針if root.Right == nil {return root.Left}if root.Left == nil {return root.Right}// 前驅的方法來替換當前節點max := root.Leftfor max.Right != nil {max = max.Right}root.Val = max.Valroot.Left = deleteMax(root.Left)return root}func deleteMax(root *TreeNode) *TreeNode {if root.Right == nil {left := root.Leftroot.Left = nilreturn left}root.Right = deleteMax(root.Right)return root}/*遞歸解法：1.找到需要刪除的節點2.刪除的節點只有右子樹或者左子樹，直接將右子樹或者左子樹的根節點當作這個刪除的節點3.刪除的節點左右子樹都存在的情況下，左子樹的最大節點也叫做前驅當作刪除節點，或者將右子樹的最小節點也就稱作后驅當作刪除節點。*/
看完上述內容，你們掌握如何刪除二叉樹中的節點的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
