no message

Chris Wu · Chris Wu · commit cebd5c6f2c88 · 2020-04-20T19:50:40.000+08:00
diff --git a/problems/diameter-of-binary-tree.py b/problems/diameter-of-binary-tree.py
@@ -24,4 +24,59 @@ def traverse(node):
         
         #iterate through the tree
         traverse(root)
-        return self.diameter
+        return self.diameter
+
+#2020
+class Solution(object):
+    def diameterOfBinaryTree(self, root):
+        def getMaxDepth(node):
+            if not node: return 0
+
+            l, r = getMaxDepth(node.left), getMaxDepth(node.right)
+            self.ans = max(self.ans, l+r)
+            return max(l, r)+1 #add the node it self
+
+        if not root: return 0
+        self.ans = float('-inf')
+        getMaxDepth(root)
+        return self.ans
+"""
+What we want to find?
+From an unknown node, that its max_depth_from_left (`l`) + max_depth_from_right (`r`) is the biggest.
+The node that generate this number could be from any node, so we iterate through every node to update `ans`.
+In other words, to find the answer, we need to check every node, if the max diameter pass through here.
+"""
+
+# from collections import defaultdict
+# class Solution(object):
+#     def diameterOfBinaryTree(self, root):
+#         def getLeftLength(node):
+#             if not node: return -1
+#             if not (node in record and 'left' in record[node]):
+#                 record[node]['left'] = max(getLeftLength(node.left), getRightLength(node.left))+1
+#             return record[node]['left']
+            
+#         def getRightLength(node):
+#             if not node: return -1
+#             if not (node in record and 'right' in record[node]):
+#                 record[node]['right'] = max(getLeftLength(node.right), getRightLength(node.right))+1
+#             return record[node]['right']
+        
+#         if not root: return 0
+        
+#         record = defaultdict(dict)
+#         ans = float('-inf')
+#         stack = []
+#         stack.append(root)
+        
+#         while stack:
+#             node = stack.pop()
+#             if not node: continue
+            
+#             d = getLeftLength(node)+getRightLength(node)
+#             ans = max(ans, d)
+#             stack.append(node.left)
+#             stack.append(node.right)
+            
+#         return ans
+
diff --git a/problems/sum-root-to-leaf-numbers.py b/problems/sum-root-to-leaf-numbers.py
@@ -0,0 +1,18 @@
+class Solution(object):
+    def sumNumbers(self, root):
+        if not root: return 0
+        ans = 0
+        stack = []
+        stack.append((root, ''))
+        
+        while stack:
+            node, total = stack.pop()
+            total += str(node.val)
+            if not node.left and not node.right:
+                ans += int(total)
+                continue
+            if node.left:
+                stack.append((node.left, total))
+            if node.right:
+                stack.append((node.right, total))
+        return ans
