more trees

keon · keon · commit 2d4276c746a0 · 2016-12-03T07:56:07.000-05:00
diff --git a/stack/longest_abs_path.py b/stack/longest_abs_path.py
@@ -33,7 +33,7 @@
             # print("maxlen: ", maxLength)
     # return maxLength
 
-def lengthLongestPath(input):
+def length_longest_path(input):
     """
     :type input: str
     :rtype: int
diff --git a/string/missing_ranges.py b/string/missing_ranges.py
@@ -0,0 +1,27 @@
+## find missing ranges between low and high in the given array.
+# ex) [3, 5] lo=1 hi=10 => answer: [1->2, 4, 6->10]
+
+def missing_ranges(nums, lo, hi):
+    res = []
+    next_num = lo
+    for num in nums:
+        if num < next_num:
+            continue
+        if num == next_num:
+            next_num += 1
+            continue
+        res.append(get_range(next_num, num-1))
+        next_num = num + 1
+    if next_num <= hi:
+        res.append(get_range(next_num, hi))
+    return res
+
+def get_range(n1, n2):
+    if n1 == n2:
+        return str(n1)
+    else:
+        return str(n1) + "->" + str(n2)
+
+nums = [3, 5, 10, 11, 12, 15, 19]
+print("original:", nums)
+print("missing range: ", missing_ranges(nums,0,20))
diff --git a/tree/BSTIterator.py b/tree/BSTIterator.py
@@ -0,0 +1,24 @@
+
+class BSTIterator:
+    def __init__(self, root):
+        self.stack = []
+        while root:
+            self.stack.append(root)
+            root = root.left
+
+    def has_next(self):
+        return bool(self.stack)
+
+    def next(self):
+        node = stack.pop()
+        tmp = node
+        if tmp.right:
+            tmp = tmp.right
+            while tmp:
+                self.stack.append(tmp)
+                tmp = tmp.left
+        return node.val
+
+
+
+
diff --git a/tree/array2bst.py b/tree/array2bst.py
@@ -0,0 +1,9 @@
+
+def array2bst(nums):
+    if not nums:
+        return None
+    mid = len(nums)//2
+    node = Node(nums[mid])
+    node.left = array2bst(nums[:mid])
+    node.right = array2bst(nums[mid+1:])
+    return node
diff --git a/tree/is_balanced.py b/tree/is_balanced.py
@@ -0,0 +1,33 @@
+
+def is_balanced(root):
+    """
+    O(N) solution
+    """
+    return -1 != get_depth(root)
+
+def get_depth(root):
+    """
+    return 0 if unbalanced else depth + 1
+    """
+    if not root:
+        return 0
+    left  = get_depth(root.left)
+    right = get_depth(root.right)
+    if abs(left-right) > 1:
+        return -1
+    return 1 + max(left, right)
+
+################################
+
+def is_balanced(root):
+    """
+    O(N^2) solution
+    """
+    left = max_height(root.left)
+    right = max_height(root.right)
+    return abs(left-right) <= 1 and is_balanced(root.left) and is_balanced(root.right)
+
+def max_height(root):
+    if not root:
+        return 0
+    return max(max_height(root.left), max_height(root.right)) + 1
diff --git a/tree/is_symmetric.py b/tree/is_symmetric.py
@@ -0,0 +1,14 @@
+
+def is_symmetric(root):
+    if not root:
+        return True
+    return helper(root.left, root.right)
+
+def helper(p, q):
+    if not p and not q:
+        return True
+    if not p or not q or q.val != p.val:
+        return False
+    return helper(p.left, q.right) and helper(p.right, q.left)
+
+
diff --git a/tree/max_height.py b/tree/max_height.py
@@ -1,5 +1,46 @@
+class Node():
+    def __init__(self, val = 0):
+        self.val = val
+        self.left = None
+        self.right = None
 
-def maxDepth(root):
+# def max_height(root):
+    # if not root:
+        # return 0
+    # return max(maxDepth(root.left), maxDepth(root.right)) + 1
+
+# iterative
+def max_height(root):
     if not root:
         return 0
-    return max(maxDepth(root.left), maxDepth(root.right)) + 1
+    height = 0
+    queue = [root]
+    while queue:
+        height += 1
+        level = []
+        while queue:
+            node = queue.pop(0)
+            if node.left:
+                level.append(node.left)
+            if node.right:
+                level.append(node.right)
+        queue = level
+    return height
+
+def print_tree(root):
+    if root:
+        print(root.val)
+        print_tree(root.left)
+        print_tree(root.right)
+
+tree = Node(10)
+tree.left = Node(12)
+tree.right = Node(15)
+tree.left.left  = Node(25)
+tree.left.left.right  = Node(100)
+tree.left.right = Node(30)
+tree.right.left = Node(36)
+
+height = max_height(tree)
+print_tree(tree)
+print("height:", height)
diff --git a/tree/max_path_sum.py b/tree/max_path_sum.py
@@ -0,0 +1,14 @@
+
+maximum = float("-inf")
+
+def max_path_sum(root):
+    helper(root)
+    return maximum
+
+def helper(root):
+    if not root:
+        return 0
+    left = helper(root.left)
+    right = helper(root.right)
+    maximum = max(maximum, left+right+root.val)
+    return root.val + max(left, right)
diff --git a/tree/min_height.py b/tree/min_height.py
@@ -0,0 +1,46 @@
+class Node():
+    def __init__(self, val = 0):
+        self.val = val
+        self.left = None
+        self.right = None
+
+def min_height_recursive(root):
+    if not root:
+        return 0
+    return max(maxDepth(root.left), maxDepth(root.right)) + 1
+
+# iterative
+def min_height(root):
+    if not root:
+        return 0
+    height = 0
+    queue = [root]
+    while queue:
+        height += 1
+        level = []
+        while queue:
+            node = queue.pop(0)
+            if node.left:
+                level.append(node.left)
+            if node.right:
+                level.append(node.right)
+        queue = level
+    return height
+
+def print_tree(root):
+    if root:
+        print(root.val)
+        print_tree(root.left)
+        print_tree(root.right)
+
+tree = Node(10)
+tree.left = Node(12)
+tree.right = Node(15)
+tree.left.left  = Node(25)
+tree.left.left.right  = Node(100)
+tree.left.right = Node(30)
+tree.right.left = Node(36)
+
+height = max_height(tree)
+print_tree(tree)
+print("height:", height)
