力扣 树相关题目 Python

 递归的判断当前节点的左右子树是否对称

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def check(self,p,q):
        #如果左右同时为空
        if p is None and q is None:
            #是轴对称的
            return True
        #如果只有一个为空
        if p is None or q is None:
            #不是对称的
            return False
        #都不为空
        #则判断左右的值是否相同
        #以及递归的判断左右的左右是否轴对称
        return p.val==q.val and self.check(p.left,q.right) and self.check(p.right,q.left)
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.check(root,root)

 当前节点的最大深度是其左右子树最大深度+1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        #如果当前节点为空
        if root is None:
            return 0
        #递归的求当前节点左右树最大深度
        else:
            left_height=self.maxDepth(root.left)
            right_height=self.maxDepth(root.right)
            #当前节点的最大深度
            return max(left_height,right_height)+1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        #最终结果
        #当前路径上只有一个节点
        self.ans=1
        #求经过root的最长路径所包含的节点数
        def depth(root):
            #空的话返回0
            if root is None:
                return 0
            #递归的求左树最长路径所包含的节点数
            l=depth(root.left)
            #递归的求右树最长路径所包含的节点数
            r=depth(root.right)
            #更新最终结果
            self.ans=max(self.ans,l+r+1)
            return max(l,r)+1
        depth(root)
        #直径为最长路径所包含的节点数-1
        return self.ans-1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        #如果节点为空
        if root is None:
            return False
        #如果只有根节点
        if root.left is None and root.right is None:
            return targetSum==root.val
        #进入左右子树递归判断
        return self.hasPathSum(root.left,targetSum-root.val) or self.hasPathSum(root.right,targetSum-root.val)

先翻转左子树，然后翻转右子树，最后翻转当前节点

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return None
        left=self.invertTree(root.left)
        right=self.invertTree(root.right)
        root.left,root.right=right,left
        return root