原题
给定一棵具有不同节点值的二叉查找树，删除树中与给定值相同的节点。如果树中没有相同值的节点，就不做任何处理。你应该保证处理之后的树仍是二叉查找树。
样例
给出如下二叉查找树：
5
/ \
3 6
/ \
2 4
删除节点3之后，你可以返回：
5
/ \
2 6
\
4
或者：
5
/ \
4 6
/
2
解题思路
- 首先Inorder遍历整棵树，当数值不等于想要删除的节点的数值时，把节点加入数组
- 利用刚刚构建的中序遍历的数组重新建立新的搜索二叉树
完整代码
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: The root of the binary search tree.
@param value: Remove the node with given value.
@return: The root of the binary search tree after removal.
"""
ans = []
def inorder(self, root, value):
if root is None:
return
self.inorder(root.left, value)
if root.val != value:
self.ans.append(root.val)
self.inorder(root.right, value)
def build(self, l, r):
if l == r:
node = TreeNode(self.ans[l])
return node
if l > r:
return None
mid = (l+r) / 2
node = TreeNode(self.ans[mid])
node.left = self.build(l, mid-1)
node.right = self.build(mid+1, r)
return node
def removeNode(self, root, value):
# write your code here
self.inorder(root, value)
return self.build(0, len(self.ans)-1)
