add

Jack-Lee-Hiter · Jack-Lee-Hiter · commit 9e6c23d8f45d · 2016-08-14T10:45:05.000+08:00
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/Target Offer/二叉树的下一个结点.py b/Target Offer/二叉树的下一个结点.py
@@ -26,4 +26,33 @@ def GetNext(self, pNode):
                 pCurrent = pParent
                 pParent = pCurrent.next
             pNext = pParent
+        return pNext
+
+class Solution2:
+    def GetNext(self, pNode):
+        # 输入是一个空节点
+        if pNode == None:
+            return None
+        # 注意当前节点是根节点的情况。所以在最开始设定pNext = None, 如果下列情况都不满足, 说明当前结点为根节点, 直接输出None
+        pNext = None
+        # 如果输入节点有右子树，则下一个结点是当前节点右子树中最左节点
+        if pNode.right:
+            pNode = pNode.right
+            while pNode.left:
+                pNode = pNode.left
+            pNext = pNode
+        else:
+            # 如果当前节点有父节点且当前节点是父节点的左子节点, 下一个结点即为父节点
+            if pNode.next and pNode.next.left == pNode:
+                pNext = pNode.next
+            # 如果当前节点有父节点且当前节点是父节点的右子节点, 那么向上遍历
+            # 当遍历到当前节点为父节点的左子节点时, 输入节点的下一个结点为当前节点的父节点
+            elif pNode.next and pNode.next.right == pNode:
+                pNode = pNode.next
+                while pNode.next and pNode.next.right == pNode:
+                    pNode = pNode.next
+                # 遍历终止时当前节点有父节点, 说明当前节点是父节点的左子节点, 输入节点的下一个结点为当前节点的父节点
+                # 反之终止时当前节点没有父节点, 说明当前节点在位于根节点的右子树, 没有下一个结点
+                if pNode.next:
+                    pNext = pNode.next
         return pNext
diff --git a/Target Offer/对称的二叉树.py b/Target Offer/对称的二叉树.py
@@ -20,4 +20,71 @@ def selfIsSymmetrical(self, pRoot1, pRoot2):
         if pRoot1.val != pRoot2.val:
             return False
         return self.selfIsSymmetrical(pRoot1.left, pRoot2.right) and self.selfIsSymmetrical(pRoot1.right, pRoot2.left)
+# 非递归实现判断二叉树是否对称
+# 利用前序遍历
+class Solution2:
+    def isSymmetrical(self, pRoot):
+        preList = self.preOrder(pRoot)
+        mirrorList = self.mirrorPreOrder(pRoot)
+        if preList == mirrorList:
+            return True
+        return False
+
+    def preOrder(self, pRoot):
+        if pRoot == None:
+            return [None]
+        treeStack = []
+        output = []
+        pNode = pRoot
+        while pNode or len(treeStack) > 0:
+            while pNode:
+                treeStack.append(pNode)
+                output.append(pNode.val)
+                pNode = pNode.left
+                if not pNode:
+                    output.append(None)
+            if len(treeStack):
+                pNode = treeStack.pop()
+                pNode = pNode.right
+                if not pNode:
+                    output.append(None)
+        return output
+
+    def mirrorPreOrder(self, pRoot):
+        if pRoot == None:
+            return [None]
+        treeStack = []
+        output = []
+        pNode = pRoot
+        while pNode or len(treeStack) > 0:
+            while pNode:
+                treeStack.append(pNode)
+                output.append(pNode.val)
+                pNode = pNode.right
+                if not pNode:
+                    output.append(None)
+            if len(treeStack):
+                pNode = treeStack.pop()
+                pNode = pNode.left
+                if not pNode:
+                    output.append(None)
+        return output
+
+pNode1 = TreeNode(8)
+pNode2 = TreeNode(6)
+pNode3 = TreeNode(10)
+pNode4 = TreeNode(5)
+pNode5 = TreeNode(7)
+pNode6 = TreeNode(9)
+pNode7 = TreeNode(11)
+
+pNode1.left = pNode2
+pNode1.right = pNode3
+pNode2.left = pNode4
+pNode2.right = pNode5
+pNode3.left = pNode6
+pNode3.right = pNode7
 
+S = Solution2()
+result = S.isSymmetrical(pNode1)
+print(result)
