翻转二叉树

翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

翻转二叉树-递归

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(root):
            if not root:
                return None
            root.left,root.right = root.right,root.left
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return root

就是在前序遍历前交换左右子树

对称二叉树

对称二叉树
给你一个二叉树的根节点 root ，检查它是否轴对称。

对称二叉树-递归

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        return self.compare(root.left,root.right)
        
    def compare(self,left,right):
        if left != None and right == None:
            return False
        elif left == None and right != None:
            return False
        elif left == None and right == None:
            return True
        elif left.val != right.val:
            return False
        outside = self.compare(left.left,right.right)
        inside = self.compare(left.right,right.left)

        return inside and outside

在后续遍历的基础上，判断以 left 为根的子树和以 right 为根的子树，是否互为镜像，为了让两棵子树互为镜像，必须满足以下三个条件：
它们的根节点值必须相同。

left 子树的左孩子，必须和 right 子树的右孩子互为镜像。
left 子树的右孩子，必须和 right 子树的左孩子互为镜像。

二叉树的最大深度

二叉树的最大深度
给你一个二叉树的根节点 root ，返回它的最大深度。

二叉树的最大深度-递归

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.getdeepth(root)
    def getdeepth(self,node):
        if not node:
            return 0
        leftdeepth = self.getdeepth(node.left)
        rightdeepth = self.getdeepth(node.right)
        deepth = max(leftdeepth,rightdeepth) + 1
        return deepth

首先区分高度和深度

高度：指的是从根节点到叶子节点的最长路径上的节点数。
深度：指的是从根节点到当前节点的路径上的节点数。
所以这里可以用根节点的高度来表示二叉树的最大深度，而求根节点的高度可以用后序遍历。
并且初始深度为0，当前节点的深度，等于其左右子树中较深的那一个的深度，再加上当前节点自己这一层

二叉树的最小深度

二叉树的最小深度
给你一个二叉树的根节点 root ，返回它的最小深度。

二叉树的最小深度-递归

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        return self.getdep(root)

    def getdep(self,node):
        if not node:
            return 0
        leftdpt = self.getdep(node.left)
        rightdpt = self.getdep(node.right)
        if leftdpt == 0 and rightdpt:
            return 1 + rightdpt
        if leftdpt and rightdpt == 0:
            return 1 + leftdpt
        return min(rightdpt,leftdpt)+1