代码随想录day20 || 235 二叉搜索树最近公共祖先，701 二叉搜索树插入，450，二叉搜索树删除节点

235 二叉搜索树最近公共祖先

unc lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	// 本题相较于普通二叉树寻找最近公共祖先加了题设条件二叉搜索树，所以使用二叉搜索树特性
	// 如果root 大于两个目标节点，那么目标都在root左子树
	// 如果root 小于两个目标节点，那么目标都是root右子树
	// 如果root == 任何一个目标，或者root大于一个小于另一个目标，那么root就是最近公共祖先
	if root == nil {
		return nil
	}

	// 使用后序traversal
	var left, right *TreeNode
	if root.Val >= p.Val && root.Val <= q.Val ||
		root.Val <= p.Val && root.Val >= q.Val {
		return root
	}

	if root.Val > p.Val && root.Val > q.Val {
		left = lowestCommonAncestor(root.Left, p, q)
	}
	if root.Val < p.Val && root.Val < q.Val {
		right = lowestCommonAncestor(root.Right, p, q)
	}

	if left != nil {
		return left
	}
	if right != nil {
		return right
	}

	return nil
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	// 迭代法
	if root == nil {
		return nil
	}

	// 使用后序traversal
	cur := root
	for (cur != nil) {
		if cur.Val > p.Val && cur.Val > q.Val {
			cur = cur.Left
		}else if cur.Val < p.Val && cur.Val < q.Val {
			cur = cur.Right
		}else  {
			return cur
		}
	}
	return nil
}

701 二叉搜索树插入操作

func insertIntoBST(root *TreeNode, val int) *TreeNode {
	// 思路1， 任何插入的节点都可以插入成为叶子节点中，本题并没有要求平衡，所以随意
	node := &TreeNode{val, nil, nil}
	if root == nil {
		return node
	}
	insert(root, node)
	return root
}

func insert(root, node *TreeNode) {
	if root.Val > node.Val {
		if root.Left == nil {
			root.Left = node
		}else {
			insert(root.Left, node)
		}
	}

	if root.Val < node.Val {
		if root.Right == nil {
			root.Right = node
		} else {
			insert(root.Right, node)
		}
	}
}

450 二叉搜索树删除节点

func deleteNode(root *TreeNode, key int) *TreeNode {
	// 歪门邪道思路，遍历二叉树，然后针对每一个节点插入
	if root == nil {
		return nil
	}

	var newRoot *TreeNode
	q := list.New()
	q.PushBack(root)
	for q.Len() > 0 {
		node := q.Remove(q.Front()).(*TreeNode)
		if node.Val != key {
			newRoot = insert(newRoot, node.Val)
		}
		if node.Left != nil {
			q.PushBack(node.Left)
		}
		if node.Right != nil {
			q.PushBack(node.Right)
		}
	}
	return newRoot
}

//func inorder (root *TreeNode, res *[]int){
//	if root == nil {
//		return
//	}
//	inorder(root.Left, res)
//	*res = append(*res, root.Val)
//	inorder(root.Right, res)
//}

func insert (root *TreeNode, val int) *TreeNode{
	if root == nil {
		root = &TreeNode{val, nil, nil}
		return root
	}
	if root.Val > val {
		if root.Left == nil {
			root.Left = &TreeNode{val, nil, nil}
		}else {
			insert(root.Left, val)
		}
	}

	if root.Val < val {
		if root.Right == nil {
			root.Right = &TreeNode{val, nil, nil}
		}else {
			insert(root.Right, val )
		}
	}
	return root
}

// 删除叶子节点：直接删除该节点。
// 删除只有一个子节点的节点：将该节点的父节点指向该节点的子节点。
// 删除有两个子节点的节点：找到该节点的中序后继或中序前驱，用后继或前驱替换该节点，然后删除后继或前驱。


func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Left == nil && root.Right == nil && root.Val == key{
		return nil
	}

	// Find the node to be deleted and its parent.
	var pre *TreeNode
	cur := root
	for cur != nil && cur.Val != key{
		pre = cur
		if key < cur.Val {
			cur = cur.Left
		} else {
			cur = cur.Right
		}
	}
	// If the node to be deleted is not found, return the original root.
	if cur == nil {
		return root
	}

	// Case 1: Node to be deleted is a leaf node.
	if cur.Left == nil && cur.Right == nil {
		if pre == nil {
			root = nil
		}else if pre.Left == cur {
			pre.Left = nil
		}else {
			pre.Right = nil
		}
		return root
	}

	// Case 2: Node to be deleted has only one child.
	if cur.Left != nil && cur.Right == nil {
		if pre == nil {
			root = cur.Left
		}else if pre.Left == cur {
			pre.Left = cur.Left
		}else {
			pre.Right = cur.Left
		}
		return root
	}
	if cur.Right != nil  && cur.Left == nil{
		if pre == nil {
			root = cur.Right
		}else if pre.Left == cur {
			pre.Left = cur.Right
		}else {
			pre.Right = cur.Right
		}
		return root
	}

	// Case 3: Node to be deleted has two children.
	// Find the inorder successor (smallest in the right subtree).
	successorParent := cur
	successor := cur.Right
	for successor.Left != nil {
		successorParent = successor
		successor = successor.Left
	}

	// Replace node's value with successor's value.
	cur.Val = successor.Val

	// Delete the successor node.
	if successorParent.Left == successor {
		successorParent.Left = successor.Right
	} else {
		successorParent.Right = successor.Right
	}

	return root
}