利特代码-5.10[965。单值二叉树,242。有效字母异形词,*236。二叉树最近的共同祖先(Python实现),leetcode510965,异位,公共,python


题目1

在这里插入图片描述

题解1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isUnivalTree(self, root: TreeNode) -> bool:
        if root is None:
            return True
        if root.left and root.val != root.left.val:
            return False
        if root.right and root.val != root.right.val:
            return False 
        return self.isUnivalTree(root.right) and self.isUnivalTree(root.left)

附上题目链接

题目2

在这里插入图片描述

题解2

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        """
            方法一,遍历替换
        """
        # 判断长度是否相等
        if len(s) != len(t):
            return False
        for word in s:
            t = t.replace(word,'',1)
        return len(t) == 0


        """
            方法二, 哈希表
        """
        from collections import Counter
        s = Counter(s)
        t = Counter(t)
        return s == t

        """
            方法三,排序
        """
        return sorted(s) == sorted(t)

附上题目链接

题目3

在这里插入图片描述

题解3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
            思路:由于是普通的二叉树,只能用搜索的办法,即前序遍历法
            1. 当root就是p或者q的时候,最近公共祖先就是root;
            2. 当root为空时,返回root;
            3. 当p,q同时出现在root的左右子树时,那么root就是最近的公共祖先;
            4. 当p,q在root的左子树,那么root.left
            5. 当p,q在root的右子树,那么root.right
        """
        if root is None or root is p or root is q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        # 判断p,q那一边
        if not left:
            return right
        if not right:
            return left
        return root

附上题目链接