算法训练营day19,二叉树8-2
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
/*本题比较难，删除节点要分五种情况考虑
1.没有找到要删除的节点
2.找到要删除的节点是叶子节点
3.找到要删除的节点，左指针不为空，右指针为空
4.找到要删除的节点，左指针为空，右指针不为空
5.找到要删除的节点，左指针不为空，右指针不为空,这种情况最复杂，需要调整二叉树结构，既可以让左子树继承，也可以让右子树继承
*/
//根据上述分析，第五点让右子树继承写法
func deleteNode(root *TreeNode, key int) *TreeNode {
//1.未找到要删除的节点
if root == nil {
return root
}
if root.Val == key {
//2.找到要删除的节点是叶子节点
if root.Right == nil && root.Left == nil {
return nil
// 3.找到要删除的节点，左指针不为空，右指针为空
} else if root.Left != nil && root.Right == nil {
return root.Left
//4.找到要删除的节点，左指针为空，右指针不为空
} else if root.Left == nil && root.Right != nil {
return root.Right
} else {
//5.找到要删除的节点，左指针不为空，右指针不为空,让右子树继承
cur := root.Right
for cur.Left != nil {
cur = cur.Left
}
cur.Left = root.Left
return root.Right
}
//因为是而二叉搜索树key比root值小，向左递归
} else if key < root.Val {
root.Left = deleteNode(root.Left, key)
//比root值大向右递归
} else if key > root.Val {
root.Right = deleteNode(root.Right, key)
}
return root
}
//第五点让左子树继承写法
func deleteNode(root *TreeNode, key int) *TreeNode {
if root == nil {
return root
}
if root.Val == key {
if root.Right == nil && root.Left == nil {
return nil
} else if root.Left != nil && root.Right != nil {
cur := root.Left
for cur.Right != nil {
cur = cur.Right
}
cur.Right = root.Right
return root.Left
} else if root.Left != nil {
return root.Left
} else {
return root.Right
}
} else if key < root.Val {
root.Left = deleteNode(root.Left, key)
} else if key > root.Val {
root.Right = deleteNode(root.Right, key)
}
return root
}