Merge pull request gzc426#330 from Scottnan/master

gzc426 · web-flow · commit e9f88618385b · 2018-12-06T22:07:40.000+08:00
Create Despacito.md
diff --git a/2018.12.07-leetcode104/Despacito.md b/2018.12.07-leetcode104/Despacito.md
@@ -0,0 +1,44 @@
+# LeetCode 104 Maximum Depth of Binary Tree
+## 1. Description
+
+Given a binary tree, find its maximum depth.
+
+The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
+
+Note: A leaf is a node with no children.
+
+Example:
+
+Given binary tree [3,9,20,null,null,15,7],
+
+       3
+      / \
+     9  20
+        / \
+       15  7
+
+return its depth = 3.
+
+## 2. Solution
+
+```python
+# Definition for a binary tree node.
+# class TreeNode:
+#     def __init__(self, x):
+#         self.val = x
+#         self.left = None
+#         self.right = None
+
+class Solution:
+    def maxDepth(self, root):
+        """
+        :type root: TreeNode
+        :rtype: int
+        """
+        if root == None:
+            return 0
+        else:
+            left = self.maxDepth(root.left)
+            right = self.maxDepth(root.right)
+            return max(left, right) + 1
+```
diff --git a/2018.12.08-leetcode105/Despacito.md b/2018.12.08-leetcode105/Despacito.md
@@ -0,0 +1,46 @@
+# LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal
+## 1. Description
+Given preorder and inorder traversal of a tree, construct the binary tree.
+
+Note:
+You may assume that duplicates do not exist in the tree.
+
+For example, given
+
+preorder = [3,9,20,15,7]
+
+inorder = [9,3,15,20,7]
+
+Return the following binary tree:
+
+      3
+     / \
+    9  20
+      /  \
+     15   7
+     
+## 2. Solution
+```python
+# Definition for a binary tree node.
+# class TreeNode:
+#     def __init__(self, x):
+#         self.val = x
+#         self.left = None
+#         self.right = None
+
+class Solution:
+    def buildTree(self, preorder, inorder):
+        """
+        :type preorder: List[int]
+        :type inorder: List[int]
+        :rtype: TreeNode
+        """
+        if len(preorder) == 0:
+            return None
+        if len(preorder) == 1:
+            return TreeNode(preorder.pop(0))
+        root = TreeNode(preorder.pop(0))
+        root.left = self.buildTree(preorder[:inorder.index(root.val)], inorder[:inorder.index(root.val)])
+        root.right = self.buildTree(preorder[inorder.index(root.val):], inorder[inorder.index(root.val)+1:])
+        return root
+```
diff --git a/2018.12.09-leetcode106/Despacito.md b/2018.12.09-leetcode106/Despacito.md
@@ -0,0 +1,48 @@
+# LeetCode 106 Construct Binary Tree from Inorder and Postorder Traversal
+## 1. Description
+
+Given inorder and postorder traversal of a tree, construct the binary tree.
+
+**Note:**
+
+You may assume that duplicates do not exist in the tree.
+
+For example, given
+
+inorder = [9,3,15,20,7]
+
+postorder = [9,15,7,20,3]
+
+Return the following binary tree:
+
+      3
+     / \
+    9  20
+      /  \
+     15   7
+
+## 2. Solution
+```python
+# Definition for a binary tree node.
+# class TreeNode:
+#     def __init__(self, x):
+#         self.val = x
+#         self.left = None
+#         self.right = None
+
+class Solution:
+    def buildTree(self, inorder, postorder):
+        """
+        :type inorder: List[int]
+        :type postorder: List[int]
+        :rtype: TreeNode
+        """
+        if len(postorder) == 0:
+            return None
+        if len(postorder) == 1:
+            return TreeNode(postorder[0])
+        root = TreeNode(postorder.pop())
+        root.left = self.buildTree(inorder[:inorder.index(root.val)], postorder[:inorder.index(root.val)])
+        root.right = self.buildTree(inorder[inorder.index(root.val)+1:], postorder[inorder.index(root.val):])
+        return root
+```
diff --git a/2018.12.10-leetcode107/Despacito.md b/2018.12.10-leetcode107/Despacito.md
@@ -0,0 +1,59 @@
+# LeetCode 107 Binary Tree Level Order Traversal II
+## 1. Description
+
+Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
+
+For example:
+Given binary tree [3,9,20,null,null,15,7],
+
+      3
+     / \
+    9  20
+      /  \
+     15   7
+     
+return its bottom-up level order traversal as:
+
+```
+[
+  [15,7],
+  [9,20],
+  [3]
+]
+```
+
+## 2. Solution
+```python
+# Definition for a binary tree node.
+# class TreeNode:
+#     def __init__(self, x):
+#         self.val = x
+#         self.left = None
+#         self.right = None
+
+class Solution:
+    def levelOrderBottom(self, root):
+        """
+        :type root: TreeNode
+        :rtype: List[List[int]]
+        """
+        if root == None:
+            return []
+        tmp = [root, '#']
+        level = []
+        result = []
+        while len(tmp) > 1:
+            head = tmp.pop(0)
+            if head != '#':
+                level.append(head.val)
+                if head.left:
+                    tmp.append(head.left)
+                if head.right:
+                    tmp.append(head.right)
+            else:
+                tmp.append('#')
+                result.insert(0, level)
+                level = []
+        result.insert(0, level)
+        return result
+```
