{"id":441899,"date":"2021-04-17T01:17:05","date_gmt":"2021-04-16T17:17:05","guid":{"rendered":"http:\/\/4563.org\/?p=441899"},"modified":"2021-04-17T01:17:05","modified_gmt":"2021-04-16T17:17:05","slug":"4-15-%e4%ba%8c%e5%88%b7%e8%bf%99%e9%81%93%e5%be%ae%e8%bd%af%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%8c%e6%8a%8a%e8%ae%a8%e8%ae%ba%e9%87%8c%e7%9a%84%e8%a7%a3%e6%b3%95%e9%83%bd%e7%90%86%e4%ba%86%e4%b8%80","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=441899","title":{"rendered":"4.15 \u4e8c\u5237\u8fd9\u9053\u5fae\u8f6f\u9762\u8bd5\u9898\uff0c\u628a\u8ba8\u8bba\u91cc\u7684\u89e3\u6cd5\u90fd\u7406\u4e86\u4e00\u904d\uff01"},"content":{"rendered":"<div>\n<div>\n<div>\n<h1>                  4.15 \u4e8c\u5237\u8fd9\u9053\u5fae\u8f6f\u9762\u8bd5\u9898\uff0c\u628a\u8ba8\u8bba\u91cc\u7684\u89e3\u6cd5\u90fd\u7406\u4e86\u4e00\u904d\uff01               <\/h1>\n<p> <\/p>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : zzzrf <\/span>  <span><i><\/i> 3<\/span> <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n<div isfirst=\"1\"> <\/p>\n<h2>\u8fd9\u91cc\u662f\u9898\u76ee\u63cf\u8ff0<\/h2>\n<h3>\u6837\u4f8b 1<\/h3>\n<pre><code>\u8f93\u5165: {1,2,2,3,4,4,3} \u8f93\u51fa: true \u89e3\u91ca:     1    \/    2   2  \/  \/  3  4 4  3 {1,2,2,3,4,4,3}\u8fd9\u68f5\u4e8c\u53c9\u6811\u662f\u5bf9\u79f0\u7684 <\/code><\/pre>\n<h3>\u6837\u4f8b 2<\/h3>\n<pre><code>\u8f93\u5165: {1,2,2,#,3,#,3} \u8f93\u51fa: false \u89e3\u91ca:     1    \/    2   2           3    3 \u5f88\u663e\u7136\u8fd9\u68f5\u4e8c\u53c9\u6811\u5e76\u4e0d\u5bf9\u79f0 <\/code><\/pre>\n<h3>\u7528\u9012\u5f52\u548c\u8fed\u4ee3\u7684\u65b9\u6cd5\u6765\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898(2 \u79cd\u89e3\u6cd5)<\/h3>\n<h2>\u4ee3\u7801<\/h2>\n<pre><code>\u00b7\u00b7\u00b7 \u4f7f\u7528\u5206\u6cbb\u6cd5 Divide Conquer \u7684\u7248\u672c \"\"\" Definition of TreeNode: class TreeNode:     def __init__(self, val):         self.val = val         self.left, self.right = None, None \"\"\"  class Solution:     \"\"\"     @param root: root of the given tree     @return: whether it is a mirror of itself      \"\"\"     def isSymmetric(self, root):         if not root:             return True         return self._is_symmetric(root.left, root.right)              def _is_symmetric(self, left_root, right_root):         if left_root is None and right_root is None:             return True         if left_root is None or right_root is None:             return False         if left_root.val != right_root.val:             return False                      left = self._is_symmetric(left_root.left, right_root.right)         right = self._is_symmetric(left_root.right, right_root.left)         return left and right <\/code><\/pre>\n<h3>\u4f7f\u7528 Iteration \u7684\u7248\u672c<\/h3>\n<pre><code>\"\"\" Definition of TreeNode: class TreeNode:     def __init__(self, val):         self.val = val         self.left, self.right = None, None \"\"\"  class Solution:     \"\"\"     @param root: root of the given tree     @return: whether it is a mirror of itself      \"\"\"          def isSymmetric(self, root):         inorder = self.inorder(root, reverse=False)         reverse_inorder = self.inorder(root, reverse=True)         if inorder != reverse_inorder:             return False                      preorder = self.preorder(root, reverse=False)         reverse_preorder = self.preorder(root, reverse=True)         return preorder == reverse_preorder              def get_left(self, node, reverse):         if reverse:             return node.right         return node.left              def get_right(self, node, reverse):         if reverse:             return node.left         return node.right              def preorder(self, root, reverse):         stack = [root]         order = []         while stack:             node = stack.pop()             order.append(node.val)             right = self.get_right(node, reverse)             if right:                 stack.append(right)             left = self.get_left(node, reverse)             if left:                 stack.append(left)         return order              def inorder(self, root, reverse):         stack = []         while root is not None:             stack.append(root)             root = self.get_left(root, reverse)                      order = []         while stack:             node = stack[-1]             order.append(node.val)             right = self.get_right(node, reverse)             if right is not None:                 node = right                 while node is not None:                     stack.append(node)                     node = self.get_left(node, reverse)             else:                 stack.pop()                 while stack and self.get_right(stack[-1], reverse) == node:                     node = stack.pop()                  return order <\/code><\/pre>\n<h3>\u4f7f\u7528 BFS \u7b97\u6cd5\u7684\u7248\u672c<\/h3>\n<pre><code>\"\"\" Definition of TreeNode: class TreeNode:     def __init__(self, val):         self.val = val         self.left, self.right = None, None \"\"\"  class Solution:     \"\"\"     @param root: root of the given tree     @return: whether it is a mirror of itself      \"\"\"     def isSymmetric(self, root):         queue = [root]         while queue:             next_queue = []             for i in range(len(queue)):                 if queue[i] is None:                     continue                 next_queue.append(queue[i].left)                 next_queue.append(queue[i].right)             if not self.is_mirror(next_queue):                 return False             queue = next_queue         return True              def is_mirror(self, queue):         left, right = 0, len(queue) - 1         while left &lt; right:             if not self.is_same(queue[left], queue[right]):                 return False             left, right = left + 1, right - 1         return True              def is_same(self, node1, node2):         if node1 and node2:             return node1.val == node2.val         return node1 is None and node2 is None <\/code><\/pre>\n<\/p><\/div>\n<div> <b>\u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (<span>0<\/span>)        <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<ul>\n<li>\n","protected":false},"excerpt":{"rendered":"<p>4.15 \u4e8c\u5237\u8fd9\u9053\u5fae\u8f6f\u9762\u8bd5\u9898\uff0c\u628a\u8ba8&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/441899"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=441899"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/441899\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=441899"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=441899"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=441899"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}