原题
给定一棵二叉查找树和一个新的树节点，将节点插入到树中。
你需要保证该树仍然是一棵二叉查找树。
给出如下一棵二叉查找树，在插入节点6之后这棵二叉查找树可以是这样的：
2 2
/ \ / \
1 4 --> 1 4
/ / \
3 3 6
解题思路
- 如果root为空，给root赋值
- root不为空，根据root.val与node.val的大小去判断往左儿子走还是右儿子走
完整代码
"""
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 node: insert this node into the binary search tree.
@return: The root of the new binary search tree.
"""
def insertNode(self, root, node):
if root is None:
root = node
elif root.val > node.val:
if root.left:
self.insertNode(root.left, node)
else:
root.left = node
else:
if root.right:
self.insertNode(root.right, node)
else:
root.right = node
return root
