fix and add

Jack-Lee-Hiter · Jack-Lee-Hiter · commit 444eff2386c9 · 2016-08-10T19:06:38.000+08:00
&#20462;&#25913;&#37096;&#20998;&#20195;&#30721;&#65292;&#28155;&#21152;&#26641;&#30340;&#23485;&#24230;&#35745;&#31639;
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/Target Offer/&#21028;&#26029;&#24179;&#34913;&#20108;&#21449;&#26641;.py b/Target Offer/&#21028;&#26029;&#24179;&#34913;&#20108;&#21449;&#26641;.py
@@ -25,4 +25,34 @@ def getDepth(self, pRoot):
         if abs(left - right) > 1:
             self.flag = False
 
-        return left if left > right else right
+        return left if left > right else right
+class Solution2:
+    def getDepth(self, pRoot):
+        if pRoot == None:
+            return 0
+        return max(self.getDepth(pRoot.left), self.getDepth(pRoot.right)) + 1
+    def IsBalanced_Solution(self, pRoot):
+        if pRoot == None:
+            return True
+        if abs(self.getDepth(pRoot.left)-self.getDepth(pRoot.right)) > 1:
+            return False
+        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
+
+
+pNode1 = TreeNode(1)
+pNode2 = TreeNode(2)
+pNode3 = TreeNode(3)
+pNode4 = TreeNode(4)
+pNode5 = TreeNode(5)
+pNode6 = TreeNode(6)
+pNode7 = TreeNode(7)
+
+pNode1.left = pNode2
+pNode1.right = pNode3
+pNode2.left = pNode4
+pNode2.right = pNode5
+pNode3.right = pNode6
+pNode5.left = pNode7
+
+S = Solution2()
+print(S.getDepth(pNode1))
diff --git a/Target Offer/&#25968;&#23383;&#22312;&#25490;&#24207;&#25968;&#32452;&#20013;&#20986;&#29616;&#30340;&#27425;&#25968;.py b/Target Offer/&#25968;&#23383;&#22312;&#25490;&#24207;&#25968;&#32452;&#20013;&#20986;&#29616;&#30340;&#27425;&#25968;.py
@@ -10,8 +10,7 @@ def GetNumberOfK(self, data, k):
             length = len(data)
             first = self.GetFirstK(data, length, k, 0, length-1)
             last = self.GetLastK(data, length, k, 0, length-1)
-            print(first, last)
-            if first > -1 and last > -1:
+            if first > -1:
                 number = last - first + 1
         return number
 
@@ -23,11 +22,11 @@ def GetFirstK(self, data, length, k, start, end):
         middleData = data[middleIndex]
 
         if middleData == k:
-            if middleIndex > 0 and data[middleIndex-1] != k or middleIndex == 0:
-                return middleIndex
-            else:
+            if middleIndex > 0 and data[middleIndex-1] == k:
                 end = middleIndex - 1
-        elif data[middleIndex] > k:
+            else:
+                return middleIndex
+        elif middleData > k:
             end = middleIndex - 1
         else:
             start = middleIndex + 1
@@ -41,11 +40,11 @@ def GetLastK(self, data, length, k, start, end):
         middleData = data[middleIndex]
 
         if middleData == k:
-            if middleIndex < length - 1 and data[middleIndex+1] != k or middleIndex == length - 1:
-                return middleIndex
-            else:
+            if middleIndex < end and data[middleIndex+1] == k:
                 start = middleIndex + 1
-        elif data[middleIndex] > k:
+            else:
+                return middleIndex
+        elif middleData > k:
             end = middleIndex - 1
         else:
             start = middleIndex + 1
diff --git a/Target Offer/&#26641;&#30340;&#23485;&#24230;.py b/Target Offer/&#26641;&#30340;&#23485;&#24230;.py
@@ -0,0 +1,55 @@
+# -*- coding:utf-8 -*-
+'''
+&#27714;&#26641;&#30340;&#23485;&#24230;
+&#21363;&#26641;&#30340;&#26576;&#23618;&#25152;&#21547;&#32467;&#28857;&#25968;&#30446;&#26368;&#22810;, &#21017;&#25171;&#21360;&#20986;&#35813;&#25968;&#23383;
+'''
+
+class TreeNode:
+    def __init__(self, x):
+        self.val = x
+        self.left = None
+        self.right = None
+class Solution:
+    def widthOfTree(self, pRoot):
+        if pRoot == None:
+            return 0
+        nodeQue = [pRoot]
+        levelCount, level, maxNum = {0: 1}, 0, 1
+        while len(nodeQue):
+            tempQue = nodeQue[:levelCount[level]]
+            curNodeNum = 0
+            while len(tempQue) > 0:
+                tempQue.pop(0)
+                pNode = nodeQue.pop(0)
+                if pNode.left:
+                    nodeQue.append(pNode.left)
+                    curNodeNum += 1
+                if pNode.right:
+                    nodeQue.append(pNode.right)
+                    curNodeNum += 1
+            level += 1
+            if level not in levelCount.keys():
+                levelCount[level] = curNodeNum
+            if curNodeNum > maxNum:
+                maxNum = curNodeNum
+        return maxNum
+
+
+pNode1 = TreeNode(1)
+pNode2 = TreeNode(2)
+pNode3 = TreeNode(3)
+pNode4 = TreeNode(4)
+pNode5 = TreeNode(5)
+pNode6 = TreeNode(6)
+pNode7 = TreeNode(7)
+
+pNode1.left = pNode2
+pNode1.right = pNode3
+pNode2.left = pNode4
+pNode2.right = pNode5
+pNode3.right = pNode6
+pNode3.left = pNode7
+
+S = Solution()
+width = S.widthOfTree(pNode1)
+print(width)
