Day.26 Binary Search Tree IV

今天讲二元树的删除，特别拉一篇出来讲，是因为它满复杂，要处理的case很多。

树的删除这边会把它分成4个case

1. 左右的child都为空
   

删45，45的左右child都为空，直接把30的右child改为空

2. 左边的child有值，但右节点为空
   

删14，14有左child但没有右child，把1拉上去，30的左child接到1

3. 右边child有值，但它底下没有左child
   

删45，45有右child 60，但60底下没有左child，那就把60拉上去，60的左child接38，30的右child接60

4. 右边child有值，底下有左child
   

这时候的情境比较复杂，我们需要找右边child底下最小的值，往右边child的左child做搜寻，找到最小的值。大家可以试试看如果用54或73做替换，再用树搜寻一下51，你会发现二元树的特性被破坏，导致有些值永远找不到。

删45，右child不为空，而且60拥有左child，往左child找最小值，找到51，把51拉上来，58的左child接到54，51的左child接38 右child接60，30的右child接51。

4个case都讲完了，就可以转化为程序
这边会做leetcode的450题，leetcode有大量test case，如果都过了就证明没问题～

Leetcode #450. Delete Node in a BST

程序

func deleteNode(root *TreeNode, key int) *TreeNode {
	var preNode *TreeNode
	currentNode := root

	// 先找到要删的节点
	for {
		// 找不到
		if currentNode == nil {
			return root
		}
        
		if currentNode.Val == key {
			break
		}
        
		if key < currentNode.Val {
			// 往左找
			preNode = currentNode
			currentNode = currentNode.Left
		} else {
			// 往右找
			preNode = currentNode
			currentNode = currentNode.Right
		}
	}

	// case.1 左右chil为空
	if currentNode.Left == nil && currentNode.Right == nil {
		// 删的是root节点
		if preNode == nil {
			root = nil
			return root
		}

		if currentNode.Val < preNode.Val {
			preNode.Left = nil
		} else {
			preNode.Right = nil
		}

		return root
	}

	// case.2 左child有东西 右child为空
	if currentNode.Left != nil && currentNode.Right == nil {
		// 删的是root节点
		if preNode == nil {
			root = currentNode.Left
			return root
		}

		// 判断要接到上一个节点的左边还是加边
		if currentNode.Val < preNode.Val {
			preNode.Left = currentNode.Left
		} else {
			preNode.Right = currentNode.Left
		}

		return root
	}

	// case.3 右child有东西 但它没有左child
	if currentNode.Right != nil && currentNode.Right.Left == nil {
		// 把目前节点的左child 接到右child的左child
		currentNode.Right.Left = currentNode.Left

		// 删的是root节点
		if preNode == nil {
			root = currentNode.Right
			return root
		}

		// 判断要接到上一个节点的左边还是加边
		if currentNode.Val < preNode.Val {
			preNode.Left = currentNode.Right
		} else {
			preNode.Right = currentNode.Right
		}

		return root
	}

	// case.4 右child拥有左child
	// 从左child开始找 找到最小的值
	leftMostParent := currentNode.Right
	leftMost := currentNode.Right.Left
	for leftMost.Left != nil {
		leftMostParent = leftMost
		leftMost = leftMost.Left
	}

	leftMostParent.Left = leftMost.Right
	leftMost.Left = currentNode.Left
	leftMost.Right = currentNode.Right

	// 删的是root节点
	if preNode == nil {
		root = leftMost
		return root
	}

	if leftMost.Val < preNode.Val {
		preNode.Left = leftMost
	} else {
		preNode.Right = leftMost
	}

	return root
}

Runtime: 12 ms, faster than 86.46% of Go online submissions for Delete Node in a BST.
Memory Usage: 7.1 MB, less than 96.88% of Go online submissions for Delete Node in a BST.

大家在leetcode的soultion可以找到非常简洁的做法，有兴趣可以上去看，不过更不好理解就是了XD

终於讲完二元树的新增删除走访了QQ
链结的概念一定要先搞懂，不然树会很难理解
今天先这样~Bye~~