五. 搜索二叉树 1 Insert Node in a Bina

思路：
对比已有的node，比它小的或者相等的放在左子树，比它大的放在右子树。

"""
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):
       # write your code here
       if not root:
           new_root = node
           return new_root
       else:
           new_root = root
       while node:
           if node.val <= root.val:
               if root.left:
                   root = root.left
               else:
                   root.left = node
                   break
           else:
               if root.right:
                   root = root.right
               else:
                   root.right = node
                   break
       return new_root