add 4 leetcodes

Jack-Lee-Hiter · Jack-Lee-Hiter · commit accc4fc56949 · 2016-08-26T20:40:09.000+08:00
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/Target Offer/把二叉树打印成多行.py b/Target Offer/把二叉树打印成多行.py
@@ -10,11 +10,10 @@ def __init__(self, x):
         self.right = None
 class Solution:
     # 返回二维列表[[1,2],[4,5]]
-    def Print(self, pRoot):
+    def levelOrder(self, pRoot):
         if pRoot == None:
             return []
-        nodes = [pRoot]
-        result = []
+        nodes, res = [pRoot], []
         while nodes:
             curStack, nextStack = [], []
             for node in nodes:
@@ -23,9 +22,9 @@ def Print(self, pRoot):
                     nextStack.append(node.left)
                 if node.right:
                     nextStack.append(node.right)
-            result.append(curStack)
+            res.append(curStack)
             nodes = nextStack
-        return result
+        return res
 
 
 pNode1 = TreeNode(8)
diff --git a/leetcode/101. Symmetric Tree.py b/leetcode/101. Symmetric Tree.py
@@ -25,10 +25,11 @@ def __init__(self, x):
 class Solution(object):
     # recursive
     def isSymmetric(self, root):
-        return self.selfIsSymmetrical(root, root)
-    def selfIsSymmetrical(self, pRoot1, pRoot2):
+        return self._Symmetrical(root, root)
+    def _Symmetrical(self, pRoot1, pRoot2):
         if pRoot1 and pRoot2:
-            return pRoot1.val == pRoot2.val and self.selfIsSymmetrical(pRoot1.left, pRoot2.right) and self.selfIsSymmetrical(pRoot1.right, pRoot2.left)
+            return pRoot1.val == pRoot2.val and self._Symmetrical(pRoot1.left, pRoot2.right) and self._Symmetrical(
+                pRoot1.right, pRoot2.left)
         else:
             return pRoot1 == pRoot2
 
@@ -43,6 +44,21 @@ def isSymmetric2(self, root):
                 else:
                     now = [j for i in now if i for j in (i.left, i.right)]
         return True
+    # modify iterative(BFS)
+    def isSymmetric_2(self, root):
+        if root:
+            nodeStack = [root]
+            while nodeStack:
+                vals = [node.val if node else None for node in nodeStack]
+                if list(reversed(vals)) != vals:
+                    return False
+                else:
+                    preStack = [node for node in nodeStack if node]
+                    nodeStack = []
+                    for preNode in preStack:
+                        nodeStack.append(preNode.left)
+                        nodeStack.append(preNode.right)
+        return True
 
     # iterative(DFS)
     def isSymmetric3(self, root):
diff --git a/leetcode/102. Binary Tree Level Order Traversal.py b/leetcode/102. Binary Tree Level Order Traversal.py
@@ -0,0 +1,36 @@
+'''
+Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
+
+For example:
+Given binary tree [3,9,20,null,null,15,7],
+    3
+   / \
+  9  20
+    /  \
+   15   7
+return its level order traversal as:
+[
+  [3],
+  [9,20],
+  [15,7]
+]
+'''
+# Definition for a binary tree node.
+class TreeNode(object):
+    def __init__(self, x):
+        self.val = x
+        self.left = None
+        self.right = None
+
+class Solution(object):
+    def levelOrder(self, root):
+        if not root:
+            return []
+        res, level = [], [root]
+        while level:
+            res.append([node.val for node in level])
+            temp = []
+            for node in level:
+                temp.extend([node.left, node.right])
+            level = [node for node in temp if node]
+        return res
diff --git a/leetcode/105. Construct Binary Tree from Preorder and Inorder Traversal.py b/leetcode/105. Construct Binary Tree from Preorder and Inorder Traversal.py
@@ -0,0 +1,57 @@
+'''
+Given preorder and inorder traversal of a tree, construct the binary tree.
+'''
+class TreeNode(object):
+    def __init__(self, x):
+        self.val = x
+        self.left = None
+        self.right = None
+
+class Solution(object):
+    # recursion
+    def buildTree(self, preorder, inorder):
+        if not preorder or not inorder:
+            return
+        root = TreeNode(preorder[0])
+        ind = inorder.index(preorder.pop(0))
+        root.left = self.buildTree(preorder, inorder[0:ind])
+        root.right = self.buildTree(preorder, inorder[ind + 1:])
+        return root
+    # method2, faster!!
+    def buildTree2(self, preorder, inorder):
+        self.Ind = 0
+        ind = {val: ind for ind, val in enumerate(inorder)}
+        head = self.build(0, len(preorder) - 1, preorder, inorder, ind)
+        return head
+
+    def build(self, start, end, preorder, inorder, ind):
+        if start <= end:
+            mid = ind[preorder[self.Ind]]
+            self.Ind += 1
+            root = TreeNode(inorder[mid])
+            root.left = self.build(start, mid - 1, preorder, inorder, ind)
+            root.right = self.build(mid + 1, end, preorder, inorder, ind)
+            return root
+    # Interative
+    def buildTreeInter(self, preorder, inorder):
+        if len(preorder) == 0:
+            return None
+
+        head = TreeNode(preorder[0])
+        stack = [head]
+        preInd, inInd = 1, 0
+
+        while preInd < len(preorder):
+            temp = None
+            node = TreeNode(preorder[preInd])
+            while stack and stack[-1].val == inorder[inInd]:
+                temp = stack.pop()
+                inInd += 1
+            if temp:
+                temp.right = node
+            else:
+                stack[-1].left = node
+            stack.append(node)
+            preInd += 1
+
+        return head
diff --git a/leetcode/106. Construct Binary Tree from Inorder and Postorder Traversal.py b/leetcode/106. Construct Binary Tree from Inorder and Postorder Traversal.py
@@ -0,0 +1,41 @@
+'''
+Given inorder and postorder traversal of a tree, construct the binary tree.
+'''
+
+# Definition for a binary tree node.
+class TreeNode(object):
+    def __init__(self, x):
+        self.val = x
+        self.left = None
+        self.right = None
+
+class Solution(object):
+    def buildTree(self, inorder, postorder):
+        if not inorder or not postorder:
+            return None
+
+        root = TreeNode(postorder.pop())
+        ind = inorder.index(root.val)
+
+        root.right = self.buildTree(inorder[ind + 1:], postorder)
+        root.left = self.buildTree(inorder[:ind], postorder)
+        return root
+
+    # method2, faster!!
+    def buildTree2(self, inorder, postorder):
+        self.postInd = len(postorder) - 1
+        ind = {val: ind for ind, val in enumerate(inorder)}
+        head = self.build(0, len(postorder) - 1, inorder, postorder, ind)
+        return head
+
+    def build(self, start, end, inorder, postorder, ind):
+        if start <= end:
+            mid = ind[postorder[self.postInd]]
+            self.postInd -= 1
+            root = TreeNode(inorder[mid])
+            root.right = self.build(mid + 1, end, inorder, postorder, ind)
+            root.left = self.build(start, mid - 1, inorder, postorder, ind)
+            return root
+
+s = Solution()
+print(s.buildTree2([1,2,3,4],[2,4,3,1]))
