Datawhale组队学习笔记task2——leetcode面试题

写在前面

教程内容来自Datawhale
开源教程：https://github.com/datawhalechina/leetcode-notes/blob/main/docs/ch07/index.md
在线学习网站：https://www.datawhale.cn/learn/summary/67
ε=(´ο｀*)))唉感觉自己是个笨小孩儿，还在一直看题解

Day5题目

1.0112.路径总和

解答

思路：DFS深度优先搜索遍历，一直向下找到叶子节点（需要同时判断节点的左右子树同时为空），如果到叶子节点时sum==0，说明找到了一条符合要求的路径。

# 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 not root:return False
        if not root.left and not root.right:
            return targetSum == root.val
        return self.hasPathSum(root.left,targetSum - root.val) or self.hasPathSum(root.right,targetSum - root.val)

时间复杂度：O(n)
空间复杂度：O(1)
题解：
回溯：利用DFS找到从根节点到叶子节点的所有路径，只要有任何一条路径的和等于sum，就返回true。
（并非严格意义上的回溯法，因为没有重复利用path变量）

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

class Solution(object):
    def hasPathSum(self, root, sum):
        if not root: return False
        res = []
        return self.dfs(root, sum, res, [root.val])
        
    def dfs(self, root, target, res, path):
        if not root: return False
        if sum(path) == target and not root.left and not root.right:
            return True
        left_flag, right_flag = False, False
        if root.left:
            left_flag = self.dfs(root.left, target, res, path + [root.left.val])
        if root.right:
            right_flag = self.dfs(root.right, target, res, path + [root.right.val])
        return left_flag or right_flag

时间复杂度：O(n)
空间复杂度：O(1)
BFS：使用队列保存遍历到每个节点时的路径和，如果该节点恰好是叶子节点，并且路径和正好等于sum，说明找到了解。

# 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 not root:
            return False
        que = collections.deque()
        que.append((root,root.val))
        while que:
            node,path = que.popleft()
            if not node.left and not node.right and path == targetSum:
                return True
            if node.left:
                que.append((node.left,path + node.left.val))
            if node.right:
                que.append((node.right,path + node.right.val))
        return False

时间复杂度：O(n)
空间复杂度：O(n)

2.0113路径总和II

解答

题解：
典型的回溯问题，解法包含先序遍历+路径记录两部分：

• 先序遍历：按照“根、左、右”的顺序，遍历树的所有节点。
• 路径记录：在先序遍历中，记录从根节点到当前节点的路径。当路径满足 (1) 根节点到叶节点形成的路径 且 (2) 各节点值的和等于目标值 targetSum 时，将此路径加入结果列表。
  
  算法流程：
  函数pathSum（root，targetSum）：
  初始化：结果列表res，路径列表path
  返回值：返回res即可
  函数recur（root,tar）：
  递推参数：当前节点root,当前目标值tar。
  终止条件：若节点root为空，则直接返回
  递推工作：
  1.路径更新：将当前节点值root.val加入路径path
  2.目标值更新：tar = tar - root.val（即目标值tar从targetSum减至0）
  3.路径记录：当（1）root为叶节点且（2）路径和等于目标值，则将此路径path加入res
  4.先序遍历：递归左/右子节点
  5.路径恢复：向上回溯前，需要将当前节点从路径path中删除，即执行path.pop()

# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res,path = [],[]
        def recur(root,tar):
            if not root:return
            path.append(root.val)
            tar -= root.val
            if tar == 0 and not root.left and not root.right:
                res.append(list(path))
            recur(root.left,tar)
            recur(root.right,tar)
            path.pop()

        recur(root,targetSum)
        return res

时间复杂度：O(n)
空间复杂度：O(n)

3.0101.对称二叉树

解答

题解：
对称二叉树定义： 对于树中 任意两个对称节点 L 和 R ，一定有：
L.val = R.val ：即此两对称节点值相等。
L.left.val = R.right.val ：即 L 的 左子节点 和 R 的 右子节点 对称。
L.right.val = R.left.val ：即 L 的 右子节点 和 R 的 左子节点 对称。
根据以上规律，考虑从顶至低递归，判断每对左右节点是否对称，从而判断树是否为对称二叉树。

# 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 recur(L,R):
            if not L and not R:return True
            if not L or not R or L.val != R.val:return False
            return recur(L.left,R.right) and recur(L.right,R.left)
        return not root or recur(root.left,root.right)

时间复杂度：O(N)
空间复杂度：O(N)

Day6题目

1.0124.二叉树中的最大路径和

解答

# 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 maxPathSum(self, root: Optional[TreeNode]) -> int:
        ans = -inf
        def dfs(node:Optional[TreeNode]) -> int:
            if node is None:
                return 0 #没有节点，和为0
            l_val = dfs(node.left) #左子树最大链和
            r_val = dfs(node.right) #右子树最大链和
            nonlocal ans
            ans = max(ans,l_val + r_val + node.val) #两条链拼成路径
            return max(max(l_val,r_val) + node.val,0) #当前子树最大链和（注意这里和0取最大值）
        dfs(root)
        return ans

时间复杂度：O(n）
空间复杂度：O(n)

2.0199.二叉树的右视图

解答

思考：即找每一层最右边的节点，可以利用层次遍历。
流程：
1、初始化队列，先将二叉树的根结点放入队列；根据队列是否为空作为循环条件；
2、获取当前层的元素个数（队列长度），并将队列尾部的元素值添加到右视图中。
3、按照队列长度遍历队列中的元素，并将其左右孩子（如果存在）添加到队列尾部，然后将当前元素出队。
4、重复步骤2,3，直到队列为空。

# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:return []
        q = deque([root])
        ans = []
        while q:
            nxt = deque()
            size = len(q)
            ans.append(q[-1].val)
            for _ in range(size):
                cur = q.popleft()
                if cur.left:
                    nxt.append(cur.left)
                if cur.right:
                    nxt.append(cur.right)
            q = nxt
        return ans

时间复杂度：O(n)
空间复杂度：O(n)

3.0226.翻转二叉树

解答

思考：递归
根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。

# 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: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:return
        tmp = root.left
        root.left = self.invertTree(root.right)
        root.right = self.invertTree(tmp)
        return root

时间复杂度 O(N) ： 其中 N 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 O(N) 时间。
空间复杂度 O(N) ： 最差情况下（当二叉树退化为链表），递归时系统需使用 O(N) 大小的栈空间。

Day7题目

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

解答

题解：
前序遍历性质：节点按照【根节点 | 左子树 | 右子树】排序
前序遍历性质：节点按照【左子树 | 根节点 | 右子树】排序
算法流程：
递推参数：根节点在前序遍历的索引root、子树在中序遍历的左边界left，子树在中序遍历的右边界right
终止条件：当left > right，代表已经越过叶节点，此时返回null
递推工作：
1、建立根节点node：节点值为preorder[root]
2、划分左右子树：查找根节点在中序遍历inorder中的索引i。
3、构建左右子树：开启左右子树递归

# 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]:
        def recur(root,left,right):
            if left > right:return #递归终止
            node = TreeNode(preorder[root]) #建立根节点
            i = dic[preorder[root]] #划分根节点、左子树、右子树
            node.left = recur(root + 1,left,i - 1) #开启左子树递归
            node.right = recur(i - left + root + 1,i + 1,right) #开启右子树递归
            return node #回溯返回根节点
        dic,preorder = {},preorder
        for i in range(len(inorder)):
            dic[inorder[i]] = i
        return recur(0,0,len(inorder) - 1)

时间复杂度 O(N)
空间复杂度 O(N)

2.0098.验证二叉搜索树

解答

利用二叉搜索树的性质，即左子树的所有节点值都小于根节点值，右子树的所有节点值都大于根节点值
前序遍历：

# 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 isValidBST(self, root: Optional[TreeNode],left=-inf,right=inf) -> bool:
        if root is None:
            return True
        x = root.val
        return left < x < right and self.isValidBST(root.left,left,x) and self.isValidBST(root.right,x,right)

时间复杂度 O(N)
空间复杂度 O(N)

3.0110.平衡二叉树

解答

性质：当前树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +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 recur(root):
            if not root:return 0
            left = recur(root.left)
            if left == -1:return -1
            right = recur(root.right)
            if right == -1:return -1
            return max(left,right) + 1 if abs(left - right) <= 1 else -1
        return recur(root) != -1

时间复杂度 O(N)
空间复杂度 O(N)

Day8题目

1.0200.岛屿数量

解答

2.0695.导语的最大面积

解答

3.0129.求根节点到叶节点数字之和

解答