Merge pull request gzc426#288 from libihan/libihan-patch-1

gzc426 · web-flow · commit 66fd0154f025 · 2018-12-03T19:45:48.000+08:00
Update libh_leetcode101-Symmetric Tree
diff --git a/2018.12.04-leetcode101/李碧涵.md b/2018.12.04-leetcode101/李碧涵.md
@@ -0,0 +1,82 @@
+### [101. Symmetric Tree](https://leetcode.com/problems/symmetric-tree/description/)
+**题目描述**
+> 判断是否是镜像二叉树（对称）
+
+**例子**
+略
+
+**思想**
+（递归）
+定义一辅助函数，输入为left和right，判断是否相等。
+（迭代）
+定义两个栈，层次遍历时判断，并分别从左向右和从右向左存储。
+
+**解法1**
+递归
+```python
+# 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 isSymmetric(self, root):
+        """
+        :type root: TreeNode
+        :rtype: bool
+        """
+        if not root:
+            return True
+        return self.helper(root.left, root.right)
+    
+    def helper(self, left, right):
+        if not left and not right:
+            return True
+        if not left or not right or left.val != right.val:
+            return False
+        return self.helper(left.left, right.right) and self.helper(left.right, right.left)
+```
+**解法2**
+迭代
+```python
+# 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 isSymmetric(self, root):
+        """
+        :type root: TreeNode
+        :rtype: bool
+        """
+        if not root or not root.left and not root.right:
+            return True
+        if not root.left or not root.right:
+            return False
+        
+        queue1, queue2 = [root.left], [root.right]
+        while queue1 and queue2:
+            node1 = queue1.pop(0)
+            node2 = queue2.pop(0)
+            
+            if node1.val != node2.val:
+                return False
+            
+            if node1.left and node2.right:
+                queue1.append(node1.left)
+                queue2.append(node2.right)
+            elif node1.left or node2.right:
+                return False
+            
+            if node1.right and node2.left:
+                queue1.append(node1.right)
+                queue2.append(node2.left)
+            elif node1.right or node2.left:
+                return False
+        return True
+```
