101. Symmetric Tree (Easy)

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

# 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 helper(left,right):
            if not left:
                return not right
            if not right:
                return not left
            return left.val==right.val and helper(left.right,right.left) and helper(left.left,right.right)
        
        return helper(root,root)

102. Binary Tree Level Order Traversal (Medium)

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        if not root: return res
        queue = [root]
        while queue:
            l=len(queue)
            level = []
            for i in range(l):
                cur=queue.pop(0)
                level.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            res.append(level)
        return res    

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = collections.defaultdict(list)
        def pre(node,level):
            if not node: return
            if node:
                res[level].append(node.val)
            pre(node.left,level+1)
            pre(node.right,level+1)
        pre(root,0)
        return list(res.values())

bfs用queue，range（length）来确定要pop的元素个数。

103. Binary Tree Zigzag Level Order Traversal （Medium）

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

# 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 zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        queue = [root]
        level = 0
        res = []
        while queue:
            li_level = []
            level +=1
            l=len(queue)
            for i in range(l):
                cur=queue.pop(0)
                li_level.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            if level%2==0:
                res.append(li_level[::-1])
            else:
                res.append(li_level)
        return res
        

bfs+level counter 如果偶数，翻转。

104. Maximum Depth of Binary Tree （Easy）

# 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 not root: return 0
        return 1+max(self.maxDepth(root.left),self.maxDepth(root.right))

105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)

# 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]) -> Optional[TreeNode]:
    
        if not preorder or not inorder: return None
        
        rootval = preorder[0]
        preorder = preorder[1:]
        root = TreeNode(rootval)
        lileft=[]
        liright=[]
        left=True
        for n in inorder:
            if n!=rootval:
                if left:
                    lileft.append(n)
                else:
                    liright.append(n)
            else:
                left=False
                
        leftnode = self.buildTree([e for e in preorder if e in lileft],lileft)
        rightnode = self.buildTree([e for e in preorder if e in liright],liright)
        root.left=leftnode
        root.right=rightnode
        return root

#answer way of writting
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        
        if not preorder or not inorder: return None
        
        rootval=preorder.pop(0)

        root=TreeNode(rootval)
        
        index=inorder.index(rootval)
        
        root.left=self.buildTree(preorder,inorder[:index])
        root.right=self.buildTree(preorder,inorder[index+1:]) #if index+1<len(inorder) else None
        
        return root
                

知道使用preorder找root 然后split inorder找到左右子数，但time limit exceed。 是因为过滤preordder必须和inorder的元素一样。其实按照子树生长方式不用这层过滤。
这个题的坑在于 #rootval = preorder[0] #preorder = preorder[1:] 看似和 rootval = preorder.pop(0) 一样，但是pop方式改变了preorder， 在递归调用时候每次递归都会改变preorder的内容，前者不会，导致left right 调用时候preorder都是相同内容导致出错。

106. Construct Binary Tree from Inorder and Postorder Traversal （Medium）

# 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]) -> Optional[TreeNode]:
        if not inorder or not postorder: return None
         
        val = postorder.pop()
        ind = inorder.index(val)
        root=TreeNode(val)
       
        right = self.buildTree(inorder[ind+1:],postorder)
        left = self.buildTree(inorder[:ind],postorder)
        
        root.left = left
        root.right = right
        return root

思路： 后序遍历最后一个数为root val。 这样可在inorder中分出左右子树数据。但建立数的时候要从右子树开始然后到左子树。

107. Binary Tree Level Order Traversal II （Medium）

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to 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 levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        queue = [root]
        res = []
        while queue:
            l=len(queue)
            level = []
            for i in range(l):
                cur=queue.pop(0)
                level.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            res.append(level)
        return res[::-1]

still bfs

108. Convert Sorted Array to Binary Search Tree (Easy)

# 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums: return None
        l=0
        r=len(nums)
        m = (l+r)//2
        root=TreeNode(nums[m])
        root.left=self.sortedArrayToBST(nums[:m])
        root.right=self.sortedArrayToBST(nums[m+1:])
        return root

109. Convert Sorted List to Binary Search Tree (Medium)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# 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 sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        
        if not head:return None
        if not head.next: return TreeNode(head.val)
        #if not head.next.next: 
        #    return TreeNode(head.next.val,left=TreeNode(head.val))
        p0=head #slow
        p1=head #fast
        pre=None
        while p1 and p1.next:
            p1=p1.next.next
            pre = p0
            p0=p0.next
            
        #print(pre.val,p0.val)    
        pre.next=None
        p0next=p0.next
        p0.next=None
        
        root = TreeNode(p0.val)
        root.left = self.sortedListToBST(head)
        root.right= self.sortedListToBST(p0next)
        
        return root

细心。。。

110. Balanced Binary Tree (Easy)

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
        
        def depth(root):
            if not root: 
                return 0
            return 1+max(depth(root.left),depth(root.right))
        
        if not root: return True
        
        left=depth(root.left)
        right=depth(root.right)
        isbalanced = abs(left-right)<=1
        return isbalanced and self.isBalanced(root.left) and self.isBalanced(root.right)

这题不应该卡， 判断了左右深度差小于等于1后还需要分别判断左右子树是否也是balanced。