no message

Chris Wu · Chris Wu · commit d2624ef67787 · 2020-04-09T07:16:38.000+08:00
diff --git a/problems/balanced-binary-tree.py b/problems/balanced-binary-tree.py
@@ -0,0 +1,27 @@
+"""
+The tree is balanced if
+1. Left child and right child are balanced
+2. |left_max_depth - right_max_depth| must smaller or equal to 1
+
+So the helper() will check condition 1. and 2. by `if l!=-1 and r!=-1 and abs(l-r)<=1`
+if true, the node is balanced, return the depth
+if not, the node is not balanced, return -1
+"""
+class Solution(object):
+    def isBalanced(self, root):
+
+        def helper(node, depth):
+            if not node.left and not node.right: return depth
+            
+            l = r = depth #l: left_max_depth, r: right_max_depth
+            if node.left:
+                l = helper(node.left, depth+1)
+            if node.right:
+                r = helper(node.right, depth+1)
+
+            if l!=-1 and r!=-1 and abs(l-r)<=1:
+                return max(l, r)
+            return -1
+        
+        if not root: return True
+        return helper(root, 0)!=-1
diff --git a/problems/maximum-depth-of-binary-tree.py b/problems/maximum-depth-of-binary-tree.py
@@ -0,0 +1,21 @@
+"""
+Time complexity: O(N), N is the number of nodes. Becasue we use DFS to traverse all the nodes.
+Space complexity: O(N), N is the number of nodes. Becasue the stack may potentially store all the nodes.
+"""
+class Solution(object):
+    def maxDepth(self, root):
+        if not root: return 0
+        
+        stack = []
+        stack.append((root, 1))
+        max_depth = 0
+        
+        while stack:
+            node, depth = stack.pop()
+            max_depth = max(max_depth, depth)
+            if node.left:
+                stack.append((node.left, depth+1))
+            if node.right:
+                stack.append((node.right, depth+1))
+        return max_depth
+        
