Tree

*tree.py

merge: 617
trim: 669


617. Merge Two Binary Trees
https://leetcode.com/problems/merge-two-binary-trees/description/
Example 1:
Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7
class Solution(object):
  def mergeTrees(self, t1, t2):
      """
      :type t1: TreeNode
      :type t2: TreeNode
      :rtype: TreeNode
      """
      #runtime complexity: O(n) n= min(A of nodes, B of nodes)  space complexty: O(m)   m =depth of recursion
      if not t1:  return t2
      if not t2:  return t1

      t1.val+= t2.val
      t1.left= self.mergeTrees(t1.left, t2.left)
      t1.right= self.mergeTrees(t1.right, t2.right)

      return t1


669. Trim a Binary Search Tree
https://leetcode.com/problems/trim-a-binary-search-tree/
Example 1:
Input: 
    1
   / \
  0   2

  L = 1
  R = 2

Output: 
    1
      \
       2
Example 2:
Input: 
    3
   / \
  0   4
   \
    2
   /
  1
  L = 1
  R = 3

Output: 
      3
     / 
   2   
  /
 1	

--------------------------------------------------------------------
class Solution(object):
    def trimBST(self, root, L, R):
        """
        :type root: TreeNode
        :type L: int
        :type R: int
        :rtype: TreeNode
        """
        # runtime complexity: O(n) n= number of nodes,  space complexity: O(n)  n= call stack = number of nodes 
        if not root:    return root
        if root.val < L:    return self.trimBST(root.right, L, R)
        if root.val > R:    return self.trimBST(root.left, L, R)
        if root.left:   root.left= self.trimBST(root.left, L, R)
        if root.right:   root.right= self.trimBST(root.right, L, R)
            
        return root