{"id":3315,"date":"2018-07-26T21:18:30","date_gmt":"2018-07-27T04:18:30","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3315"},"modified":"2018-12-15T01:18:03","modified_gmt":"2018-12-15T09:18:03","slug":"leetcode-101-symmetric-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-101-symmetric-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 101. Symmetric Tree"},"content":{"rendered":"

Problem<\/h1>\n

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).<\/p>\n

For example, this binary tree\u00a0[1,2,2,3,4,4,3]<\/code>\u00a0is symmetric:<\/p>\n

    1\r\n   \/ \\\r\n  2   2\r\n \/ \\ \/ \\\r\n3  4 4  3\r\n<\/pre>\n
But the following\u00a0[1,2,2,null,3,null,3]<\/code>\u00a0is not:<\/p>\n
    1\r\n   \/ \\\r\n  2   2\r\n   \\   \\\r\n   3    3\r\n<\/pre>\n
Note:<\/b>
\nBonus points if you could solve it both recursively and iteratively.<\/p>\n
Solution: Recursion<\/strong><\/h1>\n
Time complexity: O(n)<\/p>\n
Space complexity: O(n)<\/p>\n
\n
C++<\/h2>\n
\n\n
class Solution {\r\npublic:\r\n  bool isSymmetric(TreeNode* root) {\r\n    return isMirror(root, root);\r\n  }\r\nprivate:\r\n  bool isMirror(TreeNode* root1, TreeNode* root2) {\r\n    if (!root1 && !root2) return true;\r\n    if (!root1 || !root2) return false;\r\n    return root1->val == root2->val \r\n           && isMirror(root1->right, root2->left) \r\n           && isMirror(root1->left, root2->right);\r\n  }\r\n};<\/pre>\n\n<\/div>
Python<\/h2>\n
\n\n
\"\"\"\r\nAuthor: Huahua\r\nRunning time: 48 ms\r\n\"\"\"\r\nclass Solution:\r\n  def isSymmetric(self, root):\r\n    def isMirror(root1, root2):\r\n      if not root1 and not root2: return True\r\n      if not root1 or not root2: return False\r\n      return root1.val == root2.val \\\r\n        and isMirror(root1.left, root2.right) \\\r\n        and isMirror(root2.left, root1.right)\r\n    return isMirror(root, root)<\/pre>\n<\/div><\/div>\n
Related Problems<\/strong><\/h1>\n