二叉树

是否对称树

# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def isSym(left,right):
            if not left  and not right: return True
            if not left  and  right: return False
            if  left  and not right: return False
            if left.val !=right.val:return False
            return isSym(left.left,right.right) and isSym(left.right,right.left)


        if not root:
            return True

        return isSym(root.left,root.right)

是否相同

# 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p is None and q is not None: return False
        if p is None and q is None: return True
        if p is not None and q is None: return False

        if p.val != q.val:
            return False
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

中序遍历

# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []

        def inorder(root):
            if root:
                inorder(root.left)
                result.append(root.val)
                inorder(root.right)

        inorder(root)
        return result

二叉树的最大深度

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

二叉树的层序遍历
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

# 二叉树
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        queue = []
        queue.append(root)
        res = []
        while queue:
            ll = []
            for i in range(len(queue)):
                q = queue.pop(0)
                ll.append(q.val)
                if q.left:
                    queue.append(q.left)
                if q.right:
                    queue.append(q.right)
            res.append(ll)
        return res

前序与中序遍历序列构造二叉树

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if inorder:
            # 获取根节点
            idx = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[idx])
            # 通过中序遍历将二叉树的左右节点分开，中序遍历的左边为左节点，右边为右节点
            root.left = self.buildTree(preorder, inorder[0:idx])
            root.right = self.buildTree(preorder, inorder[idx+1:])
            return root

从中序与后序遍历序列构造二叉树

# 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 buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if inorder:
            val = postorder[-1]
            n = inorder.index(val)
            root = TreeNode(val)
            root.left = self.buildTree(inorder[0:n],postorder[0:n])
            root.right = self.buildTree(inorder[n+1:],postorder[n:-1])
            return root

            # val = postorder[-1]
            # n = inorder.index(val)
            # root = TreeNode(val)#创建树
            
            # root.left = self.buildTree(inorder[:n],postorder[:n])
            # root.right = self.buildTree(inorder[n+1:],postorder[n:-1])
            # return root

翻转二叉树

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

二叉树的最小深度

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root: return 0
        stack, ans = deque([root]), 1
        while stack:
            node_num = len(stack)
            for _ in range(node_num):
                node = stack.popleft()
                if not node.left and not node.right:
                    return ans
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
            ans += 1