572. 另一个树的子树

一、572. 另一个树的子树 1.1、题目描述

1.2.1、递归

class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if not s and not t: return True
        if not s or not t: return False
        # 前序遍历， 根节点相同，依次比较左右节点
        if s.val == t.val:
            return self.isEqual(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
        # 根节点不同，从左右子树查找
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

     
    def isEqual(self, l: TreeNode, r: TreeNode) -> bool:
        if not l and not r: return True
        if not l or not r: return False
        # 根节点值相等
        # s左子树和t的左子树相等
        # s的右子树和t的右子树相等
        if l.val == r.val:
            return self.isEqual(l.left, r.left) and self.isEqual(l.right, r.right)
        return False 

1.2.2、先序遍历生成字符串

  先序遍历两个树，生成两个字符串，判断一个字符串是不是另一个字符串的子串

class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        ss = self.inorder(s)
        st = self.inorder(t)
        # print(st,ss)
        return st in ss
        
    def inorder(self,root):
        if not root:
            return '#'
        return '*'+str(root.val)+self.inorder(root.left)+self.inorder(root.right)
        # *是为了防止两个数个位数相同（比如：2，12）造成的误判，因此用一个符合标记数字开头

二、508. 出现次数最多的子树元素和 2.1、题目描述

  给出二叉树的根，找出出现次数最多的子树元素和。一个结点的子树元素和定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。然后求出出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的元素（不限顺序）。

2.2.1、后序遍历+map

class Solution:
    def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
        if not root: return []
        self.postOrder(root)
        _max = max(self.map.values())
        ret = []
        for k in self.map.keys():
            if self.map[k] == _max:
                ret.append(k)
        return ret
                    

    def __init__(self) -> None:
        self.map = {}
    def postOrder(self, root: TreeNode) -> int:
        left = 0; right = 0
        if not root:
            return 0
        if root.left:
            left = self.postOrder(root.left)
        if root.right:
            right = self.postOrder(root.right)

        _top = left + right + root.val
        if _top not in self.map:
            self.map[_top] = 0
        self.map[_top] += 1
        return _top