Day7.1 剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值
eg:
image.png
思路：遍历查找树中节点值和子树root 一样的值，匹配后顺着查看对比子树

上述的思路有两种方法：一种迭代 一种递归

方法1：迭代

难点：

  1. 对比的两个树的函数怎么写
  2. 遍历使用深度还是广度遍历 — 我感觉优先BFS

deal 1: 对比两个点

  • A不存在 — 结构上
  • A的值和B不相等 — 数值上

https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/jian-zhi-offer-26-shu-de-zi-jie-gou-die-0qjeh/

  1. def compare_tree(self,A,B):
  2.         ddque = [(A,B)]
  4.         while ddque:
  5.             node_A, node_B = ddque.pop(0)
  7.             if node_A == None or node_A.val != node_B.val :
  8.                 return False
  10.             if node_B.left:
  11.                 ddque.append((node_A.left,node_B.left))
  12.             if node_B.right:
  13.                 ddque.append((node_A.right,node_B.right))
  15.         return True

OK 有了部分代码可以写整体代码

  1. from collections import deque
  3. class Solution:
  4.     def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
  5.         if A == None or B == None:
  6.             return False
  8.         # Part1: 遍历：BFS
  9.         dquee = deque()
  10.         dquee.append(A)
  12.         while dquee:
  13.             tree_node = dquee.popleft()
  14.             # Part2: 比较
  15.             if tree_node.val == B.val:
  16.                 if self.compare_tree(tree_node,B):
  17.                     return True
  19.             if tree_node.left : dquee.append(tree_node.left)
  20.             if tree_node.right: dquee.append(tree_node.right)
  22.         return False
  23.     # 以B为标杆遍历比较
  24.     def compare_tree(self,A,B):
  25.         ddque = [(A,B)]
  27.         while ddque:
  28.             node_A, node_B = ddque.pop(0)
  30.             if node_A == None or node_A.val != node_B.val :
  31.                 return False
  33.             if node_B.left:
  34.                 ddque.append((node_A.left,node_B.left))
  35.             if node_B.right:
  36.                 ddque.append((node_A.right,node_B.right))
  38.         return True

执行用时：104 ms, 在所有 Python3 提交中击败了63.54%的用户
内存消耗：19.3 MB, 在所有 Python3 提交中击败了14.07%的用户

当然compare_tree部分的代码可以使用双向队列优化：

  1. def compare_tree(self,A,B):
  2.         ddque = deque()
  3.         ddque.append((A,B))
  4.         # ddque = [(A,B)]
  6.         while ddque:
  7.             node_A, node_B = ddque.popleft()
  9.             if node_A == None or node_A.val != node_B.val :
  10.                 return False
  12.             if node_B.left:
  13.                 ddque.append((node_A.left,node_B.left))
  14.             if node_B.right:
  15.                 ddque.append((node_A.right,node_B.right))
  17.         return True

时间会 稍稍提升
复杂度分析

m为A的节点个数，n为B的节点个数

时间复杂度：O(m * n)，遍历A：O(m)，比较A和B：O(n)
空间复杂度：O(m)，最差的情况就是遍历了A的所有节点

想更好的解决问题，我觉得递归不可避免

方法2：递归

感觉不难 但是不想看。。。哭了 等等再看 先往后做

Day7.2 剑指 Offer 27. 二叉树的镜像

输入一个二叉树，该函数输出它的镜像。— 反转二叉树
image.png

方法1：递归法

递归真tm神奇，，我感觉要理出一个套路来！！！

来来来 看看大佬的题解 — 懂了 又没全懂

  • 深度优先 — DFS

image.png

卧槽 我竟然看着上面的流程写出来代码了

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if root == None:
            return None

        tmp = TreeNode()

        tmp = self.mirrorTree(root.right)
        root.right = self.mirrorTree(root.left)
        root.left = tmp

        return root

执行用时：24 ms, 在所有 Python3 提交中击败了97.76%的用户
内存消耗：14.7 MB, 在所有 Python3 提交中击败了98.32%的用户

???? 嗯？？不过如此？？？？ 感觉就是交换两个元素的值

看看官方代码 — 简化了一丢丢而已 — 逻辑一致 

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: return
        root.left, root.right = self.mirrorTree(root.right), self.mirrorTree(root.left)
        return root

这属于 中序遍历？傻傻分不清

Day7.3 剑指 Offer 28. 对称的二叉树

判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的

返回True False
感觉树的问题基本都是迭代

方案1：迭代

BFS，广度优先，前序遍历 — 判断左右是不是一致

问题：向左还是向右迭代，，这个怎么写，先左还是先右呢 [在这里 定义一个函数]
image.png

来来来！！ 牛逼！！ — 上面的问题在这里

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root == None:
            return True

        return self.compare_LR(root.left,root.right)


    def compare_LR(self,Left,Right):

        if Left == None and Right == None:
            return True

        if Left == None or Right == None or Left.val != Right.val:  
            return False

        return self.compare_LR(Left.left,Right.right) and self.compare_LR(Left.right,Right.left)

执行用时：32 ms, 在所有 Python3 提交中击败了81.98%的用户
内存消耗：15 MB, 在所有 Python3 提交中击败了82.56%的用户