450.md

450. Delete Node in a BST

题目： https://leetcode.com/problems/delete-node-in-a-bst/

难度 : Medium

思路：

从二叉搜索树中删除节点x的方法如下:

• 如果x没有子节点，或者只有一个孩子，直接将x“切下”;

• 否则，x有两个孩子，我们用其右子树中的最小值替换掉x，然后将右子树中的这一最小值递归的“切掉”。 ​

AC代码

class Solution(object):
    def deleteNode(self, root, key):
        """
        :type root: TreeNode
        :type key: int
        :rtype: TreeNode
        """
        def findmin(root):
        	while root.left:
        		root = root.left
        	return root


        if not root : return None
    	elif key < root.val: root.left = self.deleteNode(root.left, key)
    	elif key > root.val : root.right = self.deleteNode(root.right, key)
    	else:
    		if root.left and root.right:
    			tmp = findmin(root.right)
    			root.val = tmp.val
    			root.right = self.deleteNode(root.right, tmp.val)
    		else:
    			if not root.left:
    				root = root.right
    			elif not root.right:
    				root = root.left
    	return root

​

其实这个代码还是需要花点时间来理解，需要画个图，理解这个root是每个stack return回去然后被接在原来的树上的，if 这个node并不是在node左右。