fix and add

Jack-Lee-Hiter · Jack-Lee-Hiter · commit e124be764615 · 2016-08-06T11:56:09.000+08:00
增加了二叉树的遍历以及优化部分代码
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/Target Offer/二维数组查找.py b/Target Offer/二维数组查找.py
@@ -27,11 +27,12 @@ def Find(self, array, target):
         colnum = len(array[0])
 
         # 判断非法输入
+        # 可以换成 isinstance(target, (int, float)) 进行判断
         if type(target) == float and type(array[0][0]) == int:
             target = int(target)
         elif type(target) == int and type(array[0][0]) == float:
             target = float(int)
-        elif type(target) != type(array[0][0]):
+        elif type(target) != type(array[0][0]):     # 浮点数的相等判断问题需要特别注意, 一般都是判断两个数的差值是否小于一个特别小的数。这里不展开分析。
             return False
 
         i = colnum - 1
diff --git a/Target Offer/替换空格.py b/Target Offer/替换空格.py
@@ -20,41 +20,35 @@ def replaceSpace1(self, s):
         return tempstr
 
     # 简单代码替换
+    # 在Python中str类型是不可变的类型, 使用replace语句会生成一个新的str, 原始的s还是带空格的str变量
     def replaceSpace2(self, s):
         if type(s) != str:
             return
         return s.replace(' ', '%20')
 
     # 书中给的思路
+    # 判断输入类型的时候，isinstance必须首先判断，因为如果输入为integer的话，没有len，就会直接报错
     def replaceSpace3(self, s):
-        if type(s) != str:
-            return
-        if len(s) <= 0:
-            return
+        if not isinstance(s,str) or len(s) <= 0 or s == None:
+            return ""
         spaceNum = 0
         for i in s:
             if i == " ":
                 spaceNum += 1
 
         newStrLen = len(s) + spaceNum * 2
         newStr = newStrLen * [None]
-        indexOfOriginal = len(s) - 1
-        indexOfNew = newStrLen - 1
+        indexOfOriginal, indexOfNew = len(s) - 1, newStrLen - 1
         while indexOfNew >= 0 and indexOfNew >= indexOfOriginal:
             if s[indexOfOriginal] == ' ':
-                newStr[indexOfNew] = '0'
-                newStr[indexOfNew-1] = '2'
-                newStr[indexOfNew-2] = '%'
+                newStr[indexOfNew-2:indexOfNew+1] = ['%', '2', '0']
                 indexOfNew -= 3
                 indexOfOriginal -= 1
             else:
                 newStr[indexOfNew] = s[indexOfOriginal]
                 indexOfNew -= 1
                 indexOfOriginal -= 1
-        changedStr = ''
-        for c in newStr:
-            changedStr += c
-        return changedStr
+        return "".join(newStr)
 
 
 s = 'we are happy'
diff --git a/Target Offer/递归和非递归实现二叉搜索树的三种遍历.py b/Target Offer/递归和非递归实现二叉搜索树的三种遍历.py
@@ -0,0 +1,91 @@
+# -*- coding:UTF-8 -*-
+'''
+利用递归以及非递归的方式实现二叉搜索树的前序遍历、中序遍历和后序遍历
+'''
+
+class TreeNode:
+    def __init__(self, x):
+        self.val = x
+        self.left = None
+        self.right = None
+
+class Tranversal:
+    # preorder without recursion
+    def preOrder(self, root):
+        if root == None:
+            return None
+        pNode, treeStack = root, []
+        while pNode or len(treeStack) > 0:
+            while pNode:
+                print(pNode.val)
+                treeStack.append(pNode)
+                pNode = pNode.left
+            if len(treeStack) > 0:
+                pNode = treeStack.pop()
+                pNode = pNode.right
+    # preorder with recursion
+    def preOrderRec(self, root):
+        if root != None:
+            print(root.val)
+            self.preOrderRec(root.left)
+            self.preOrderRec(root.right)
+    # inorder without recursion
+    def inOrder(self, root):
+        if root == None:
+            return
+        pNode, treeStack = root, []
+        while pNode or len(treeStack) > 0:
+            while pNode:
+                treeStack.append(pNode)
+                pNode = pNode.left
+            if len(treeStack) > 0:
+                pNode = treeStack.pop()
+                print(pNode.val)
+                pNode = pNode.right
+    # inorder with recursion
+    def inOrderRec(self, root):
+        if root != None:
+            self.inOrderRec(root.left)
+            print(root.val)
+            self.inOrderRec(root.right)
+    # postorder without recursion
+    def postOrder(self, root):
+        if root == None:
+            return
+        cur, pre, treeStack = root, None, []  # cur:current Node, pre: pre visited Node
+        treeStack.append(root)
+        while len(treeStack) > 0:
+            cur = treeStack[-1]
+            # current node doesn't have child nodes or child nodes have been visited
+            if (cur.left == None and cur.right == None) or (pre != None and (pre == cur.left or pre == cur.right)):
+                print(cur.val)
+                pre = treeStack.pop()
+            else:
+                if cur.right != None:
+                    treeStack.append(cur.right)
+                if cur.left != None:
+                    treeStack.append(cur.left)
+    # postorder with cursion
+    def postOrderRec(self, root):
+        if root:
+            self.postOrderRec(root.left)
+            self.postOrderRec(root.right)
+            print(root.val)
+
+pNode1 = TreeNode(10)
+pNode2 = TreeNode(6)
+pNode3 = TreeNode(14)
+pNode4 = TreeNode(4)
+pNode5 = TreeNode(8)
+pNode6 = TreeNode(12)
+pNode7 = TreeNode(16)
+
+pNode1.left = pNode2
+pNode1.right = pNode3
+pNode2.left = pNode4
+pNode2.right = pNode5
+pNode3.left = pNode6
+pNode3.right = pNode7
+
+S = Tranversal()
+S.postOrder(pNode1)
