1.DFS

1.1 二叉树问题

636. 函数的独占时间 - 力扣（LeetCode）
题解：二叉树在指定深度（depth）添加值为val的行。当找到depth-1行时，进行左子树右子树替换。
解法：BFSorDFS
BFS方法：通过队列存储节点有计数循环进入到depth-1层即可。跳出，替换所有depth-1层的左子树和右子树。
BFS代码：时间复杂度：O(n)(完全遍历），空间复杂度:O(n)

class Solution:
    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
        if root is None:
            return 
        if depth==1:
            return TreeNode(val,root,None)
        curlevel=[root]
        for i in range(1,depth-1):
            tmp=[]
            for node in curlevel:
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
            curlevel=tmp
        for node in curlevel:
            node.left=TreeNode(val,node.left,None)
            node.right=TreeNode(val,None,node.right)
        return root

DFS方法：注意判断root为空的情况。列出depth==1,2的特殊情况即可。
DFS代码：时间复杂度：O(n) 空间复杂度：O(n)

class Solution:
    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
        if root is None:
            return 
        if depth==1:
            return TreeNode(val,root,None)
        if depth==2:
            root.left=TreeNode(val,root.left,None)
            root.right=TreeNode(val,None,root.right)
            return root
        if depth>2:
            root.left=self.addOneRow(root.left,val,depth-1)
            root.right=self.addOneRow(root.right,val,depth-1)
            return root

2.图论：

【565】565. 数组嵌套 - 力扣（LeetCode）

一个长度为N由1，···，N-1组成的不重复数组-->组成1个或多个环（无交集）

3.【合并链表及其变体】合并链表与两数相加

2. 两数相加 - 力扣（LeetCode）

21. 合并两个有序链表 - 力扣（LeetCode）

?不用想很复杂，由于是倒序的链表，所以从个位数就对齐了，每一位上直接相加，记下是否进位就好了。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        pre=0
        cur=dum=ListNode(0)
        while l1 and l2:
            cur.next=ListNode((l1.val+l2.val+pre)%10)
            if l1.val+l2.val+pre>=10:
                pre=1
            else:
                pre=0
            cur=cur.next
            l1=l1.next
            l2=l2.next
        nex=l1 if l1 else l2
        while nex:
            cur.next=ListNode((nex.val+pre)%10)
            if nex.val+pre>=10:
                pre=1
            else:
                pre=0
            cur=cur.next
            nex=nex.next
        cur.next=ListNode(pre) if pre==1 else None
        return dum.next