dfs解决了什么问题：

(1) 图中（有向无向皆可）的符合某种特征（比如最长）的路径以及长度（2）排列组合（3） 遍历一个图（或者树）（4）找出图或者树中符合题目要求的全部方案

深度优先遍历(DFS)

基于树的DFS

需要记住递归写前序中序后序遍历二叉树的模板

1.1.1.二叉树的直径 (opens new window)

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

输入：root = [1,2]
输出：1

提示

方法：深度优先搜索

• 首先我们知道一条路径的长度为该路径经过的节点数减一，所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一。
• 而任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。
• 假设我们知道对于该节点的左儿子向下遍历经过最多的节点数 L （即以左儿子为根的子树的深度） 和其右儿子向下遍历经过最多的节点数 R（即以右儿子为根的子树的深度），那么以该节点为起点的路径经过节点数的最大值即为 L+R+1 。
• 我们记节点 node为起点的路径经过节点数的最大值为 d_node，那么二叉树的直径就是所有节点 d_node的最大值减一。
• 最后的算法流程为：我们定义一个递归函数 depth(node) 计算 d_noded，函数返回该节点为根的子树的深度。先递归调用左儿子和右儿子求得它们为根的子树的深度 L和 R ，则该节点为根的子树的深度即为 max(L,R)+1
• 该节点的 d_node值为 L+R+1
• 递归搜索每个节点并设一个全局变量 ans, 记录d_+node的最大值， 然后返回 ans-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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.ans = 1
        def depth(root):
            # 访问到空节点
            if not root:
                return 0
            # 左儿子为根的子树深度
            l = depth(root.left)
            # 右儿子为根的子树深度
            r = depth(root.right)
            # 计算路径的的深度，l + r + 1

            self.ans = max(self.ans, l + r + 1)
            # 返回该节点为根的子树的深度
            return max(l, r) + 1
        depth(root)
        return self.ans - 1

// Make sure to add code blocks to your code group

1.1.2.二叉树中的最大路径和 (opens new window)

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示

解题思路： 二叉树 abc，a 是根结点（递归中的 root），bc 是左右子结点（代表其递归后的最优解）。 最大的路径，可能的路径情况：

   a
/    \
b     c

1. b + a + c
2. b + a + a 的父结点。
3. a + c + a 的父结点。

其中情况 1，表示如果不联络父结点的情况，或本身是根结点的情况。 这种情况是没法递归的，但是结果有可能是全局最大路径和。 情况 2 和 3，递归时计算 a+b 和 a+c，选择一个更优的方案返回，也就是上面说的递归后的最优解啦。

另外结点有可能是负值，最大和肯定就要想办法舍弃负值 （max(0,x)。 但是上面 3 种情况，无论哪种，a 作为联络点，都不能够舍弃。

# 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:
        self.ans = float("-inf")

        def dfs(root):
            if not root:
                return 0
            # 递归计算左右子节点的最大贡献值
            # 只有在最大贡献值大于 0 时，才会选取对应子节点
          
            l_num = max(dfs(root.left), 0)
            r_num = max(dfs(root.right), 0)
            # 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
            # 更新答案
            self.ans = max(self.ans, l_num + r_num + root.val)
            # 返回节点的最大贡献值
            return max(l_num, r_num) + root.val
      
        dfs(root)
        return self.ans

// Make sure to add code blocks to your code group

提示

这道题说难也不难，但说容易也真不是那么容易能想到的（写得比较多，但都是心得，耐心看完就更上一层楼了）。 首先就是递归的方式，很多人都对递归一头雾水，一看就会，一写就废。不用担心，这是正常现象。 下面，我们详细解释一下这道题，顺便疏通一下递归的基本思路。

我们不要先去考虑整个递归的代码怎么去写，而是要明确一个递归的主体，就是这个递归的主体要怎么构造，然后再去想边界条件，返回值等等。

1、那么，首先我们可以假设走到了某个节点，现在要面临的问题是路径的最大值问题，显然对于这种问题，每遍历到一个节点，我们都要求出包含该节点在内的此时的最大路径，并且在之后的遍历中更新这个最大值。对于该节点来说，它的最大路径 currpath就等于左右子树的最大路径加上本身的值，也就是 currpath = left+right+node,val，但是有一个前提，我们要求的是最大路径，所以若是left或者right小于等于0了，那么我们就没有必要把这些值加上了，因为加上一个负数，会使得最大路径变小。这里的最大路径中的最其实就是一个限定条件，也就是我们常说的贪心算法，只取最大，最好，其余的直接丢弃。

2、好了，1中的主体我们已经明确了，但是还存在一个问题，那就是 left和 right具体应该怎么求，也就是 left和 right的递归形式。显然我们要把 node.left和 node.right再次传输到递归函数中，重复上述的操作。但如果到达了叶子节点，是不是需要往上一层返回了呢？那么返回值又是多少呢？ 我们要明确 left和 right的基本含义，它们表示的是最大贡献，那么一个节点的最大贡献就等于 node.val+max(left,right)，这个节点本身选上，然后从它的左右子树中选择最大的那个加上。 对于叶子节点也是这样，但是叶子节点的左右子树都为空，所以加上0，哎，注意看，此时是不是边界条件也出来了，但节点为空时，返回0 。 好了，至此循环的主体，返回值，边界条件都定义好了，那么整个递归的代码是不是就水到渠成了。这样一看递归也没什么了不起的！！！

ps:除了向下思考，其实也可以向上思考，比如还是遍历到了某个节点，那么这个节点向上一层走，是不是要有一个返回值呢，那么返回值是什么呢？是不是和自己原来需要的 right(or left)相同，只不过现在轮到自己了，自己原来需要最大贡献，那么此时返回时就返回最大贡献，自己的最大贡献不就是 node.val+max(left,right)。就像是老板一层一层的压榨员工一样。

1.1.3.翻转二叉树 (opens new window)

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

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
		# 自上向下翻转
        # 也可以自下向上
        def dfs(root):
            if not root:
                return
            
            root.left, root.right = root.right, root.left
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        queue = collections.deque([root])
        while queue:
            node = queue.popleft()

            node.left , node.right = node.right, node.left
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return root

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
  // 深度优先遍历，自下向上，先交换叶子节点
  var dfs func(root *TreeNode) *TreeNode
  dfs = func(root *TreeNode) *TreeNode{
      if root == nil{
          return root
      }
      leftNode := dfs(root.Left)
      rightNode := dfs(root.Right)
      root.Left, root.Right = rightNode, leftNode
      return root
  }
  return dfs(root)
}

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
  // 广度优先遍历
  if root == nil{
      return nil
  }
  queue := []*TreeNode{root}
  for len(queue)>0 {
      node := queue[0]
      queue = queue[1:]
      node.Left, node.Right = node.Right, node.Left
      if node.Left != nil{
          queue = append(queue, node.Left)
      }
      if node.Right != nil{
          queue = append(queue, node.Right)
      }

  }
  return root
}

// Make sure to add code blocks to your code group

1.1.4.对称二叉树 (opens new window)

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

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

# 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:
        if not root:
            return True


        def dfs(left, right):

            # 一个为空一个不为空返回fasle
            if (not left) ^ (not right):
                return False
            # 上一个判断过不同时为空的情况
            # 所以这里只要有一个为空，则两个都为空
            if not left:
                return True

            if left.val != right.val:
                return False
            return dfs(left.left, right.right) and dfs(left.right, right.left)
        return dfs(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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return False
        if (not root.left) ^( not root.right):
            return False
        
        queue = collections.deque([root.left, root.right])
        while queue:
            cur1 = queue.popleft()
            cur2 = queue.popleft()
            if (not cur1) ^ (not cur2):
                return False
            if cur1 and cur2:
                if cur1.val != cur2.val:
                    return False
                queue.append(cur1.left)
                queue.append(cur2.right)
                queue.append(cur1.right)
                queue.append(cur2.left)
        return True

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func isSymmetric(root *TreeNode) bool {
  if root== nil{
      return true
  }

  var dfs func(left *TreeNode, right *TreeNode) bool

  dfs = func(left *TreeNode, right *TreeNode) bool{
      if (left == nil) || (right == nil){
          return left == right
      }
      if left.Val != right.Val{
          return false
      }
      return dfs(left.Left, right.Right)&&dfs(left.Right, right.Left)

  }
  return dfs(root.Left, root.Right)
}

func isSymmetric(root *TreeNode) bool{
  // 广度优先
  // if root == nil{
  //     return true
  // }
  if root== nil{
      return true
  }

  queue := make([]*TreeNode, 0)
  queue = append(queue, root.Left)
  queue = append(queue, root.Right)
  for len(queue)>0{
  	node1 := queue[0]
      node2 := queue[1]
      queue = queue[2:]
      if (node1 == nil) != (node2 == nil){
          return false
      }
      if node1 == nil{
          continue
      }
      if node1.Val != node2.Val{
          return false
      }
      if node1 != nil && node2 != nil &&((node1.Left == nil) != (node2.Right== nil)){
          return false
      }
      if (node1.Right == nil) != (node2.Left == nil){
          return false
      }
      queue = append(queue, node1.Left, node2.Right, node1.Right, node2.Left)
  }

  return true
}

// Make sure to add code blocks to your code group

1.1.5.翻转等价二叉树 (opens new window)

我们可以为二叉树 T 定义一个 翻转操作 ，如下所示：选择任意节点，然后交换它的左子树和右子树。

只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转 等价 于二叉树 Y。

这些树由根节点 root1 和 root2 给出。如果两个二叉树是否是翻转 等价 的函数，则返回 true ，否则返回 false 。

示例 1：

输入：root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
输出：true
解释：我们翻转值为 1，3 以及 5 的三个节点。

示例 2:

输入: root1 = [], root2 = []
输出: true

示例 3:

输入: root1 = [], root2 = [1]
输出: false

笔记

• 这个题目本质上很简单，就是判断是否为交换的。 首先，针对树的遍历，我们绝大多数都是采用深度优先搜索遍历。 这里先确定大体的思路。

• 难点在于，如何判断呢？难点在于，如何判断呢？难点在于，如何判断呢？ 这里我们可以先不急，简单罗列一下可能存在的几种情况。

• 情况一，root1和root2相同：root1和root2一致，即root1的左子树和root2的左子树相同，root1的右子树和root2的右子树相同 情况二，root1和root2相反：root1和root2相反，即root1的左子树和root2的右子树相同，root1的右子树和root2的左子树相同 如果上面的思路搞清楚之后，结合树本身特性：子问题，子树的处理方式和原树处理方式一致子树的处理方式和原树处理方式一致子树的处理方式和原树处理方式一致，直接使用递归完事。

# 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 flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        if root1 == None or root2 == None:
            return root1 == root2
        if root1.val != root2.val:
            return False
        flag1 = self.flipEquiv(root1.left, root2.left) and (self.flipEquiv(root1.right, root2.right))
        flag2 = self.flipEquiv(root1.left, root2.right) and (self.flipEquiv(root1.right, root2.left))
        return flag1 or flag2

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func flipEquiv(root1 *TreeNode, root2 *TreeNode) bool {
  //在子节点上有两种情况，要么就是相等，要么就是翻转后相同
  if root1 == nil || root2 == nil{
      return root1 == root2
  }
  if root1.Val != root2.Val{
      return false
  }
  
  return (flipEquiv(root1.Left, root2.Left) && flipEquiv(root1.Right, root2.Right)) ||
          (flipEquiv(root1.Left, root2.Right) && flipEquiv(root1.Right, root2.Left))
}

// Make sure to add code blocks to your code group

1.1.6. 二叉树的最近公共祖先 (opens new window)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科 (opens new window)中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return None
        
        if root.val == p.val or root.val == q.val:
            return root
        
        left = lowestCommonAncestor(root.left, p, q)
        right = lowestCommonAncestor(root.right, p, q)
        if left != None and right != None:
            return root
        if left == None:
            return right
        return left

// Make sure to add code blocks to your code group

1.1.7.从前序与中序遍历序列构造二叉树 (opens new window)

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        """
        对于任意一颗树而言，前序遍历的形式总是

        [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
        即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是

        [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

        """
        
        if len(preorder) == 0:
            return None
        
        val = preorder[0]
        root = TreeNode(val=val)
        index = 0
        for index, j in enumerate(inorder):
            if val == j:
                break
        root.left = self.buildTree(preorder[1:index+1], inorder[:index])
        root.right = self.buildTree(preorder[index+1:], inorder[index+1:])

        return root

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {

  // 
  if len(preorder) == 0{
      return nil
  }

  root := &TreeNode{Val: preorder[0]}
  index := 0
  for index_, val := range inorder{
      if val == root.Val{
          index = index_
          break
      }
  }
  root.Left = buildTree(preorder[1: index+1], inorder[:index])
  root.Right = buildTree(preorder[index+1:], inorder[index+1:])
  return root
}

// Make sure to add code blocks to your code group

1.1.8.二叉树的最大深度 (opens new window)

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

注意

• 如果我们知道了左子树和右子树的最大深度 lll 和 rrr，那么该二叉树的最大深度即为max⁡(l,r)+1
• 而左子树和右子树的最大深度又可以以同样的方式进行计算。
• 因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。
• 具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在`` O(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 maxDepth(self, root: Optional[TreeNode]) -> int:
        """
        广度优先遍历，最大深度就是遍历的层数
        """
        def height(root):
            if not root:
                return 0
            return max(height(root.left), height(root.right))+1
        return height(root)

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func maxDepth(root *TreeNode) int {
  
  var dfs func(root *TreeNode) int
  dfs = func(root *TreeNode) int{
      if root == nil{
          return 0
      }
      left := dfs(root.Left) + 1
      right := dfs(root.Right) + 1
      return max(left, right)
  }
  return dfs(root)
}

// Make sure to add code blocks to your code group

1.1.9. 另一棵树的子树 (opens new window)

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

提示

使用递归方法，原函数中判断当前root和subroot的关系，如果不行则return判断root左右两边和subroot`的关系。 再定义一个递归函数，用来判断两个树是否相同。

# 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 isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:

        def helper(root, subRoot):
            if root == None and subRoot == None:
                return True
            if root == None or subRoot == None:
                return False
            if root.val != subRoot.val:
                return False 
            return helper(root.left, subRoot.left) and helper(root.right,subRoot.right)
        if not root:
            return False
        if helper(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

        

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {

  var helper func(root *TreeNode, subRoot *TreeNode) bool
  helper = func(root *TreeNode, subRoot *TreeNode) bool{
      if root == nil && subRoot == nil{
          return true
      }
      if root == nil || subRoot == nil{
          return false
      }
      if root.Val != subRoot.Val{
          return false
      }
      return helper(root.Left, subRoot.Left) && helper(root.Right, subRoot.Right)
  }
  if root == nil{
      return false
  }
  if helper(root, subRoot){
      return true
  }

  return isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}

// Make sure to add code blocks to your code group

1.1.10.二叉树中所有距离为 K 的结点 (opens new window)

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 k ，返回到目标结点 target 距离为 k 的所有结点的值的数组。

答案可以以 任何顺序 返回。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
输出：[7,4,1]
解释：所求结点为与目标结点（值为 5）距离为 2 的结点，值分别为 7，4，以及 1

示例 2:

输入: root = [1], target = 1, k = 3
输出: []

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

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        pres = dict()
        # 构建每个节点的父节点
        def helper(root, parent= None):
            if not root:
                return
            pres[root] = parent
            helper(root.left, root)
            helper(root.right, root)
        helper(root)
        ans = []

        def getDepth(root, parent=None, depth=0):
            if not root:
                return
            if depth == k:
                ans.append(root.val)
            if root.left != parent:
                getDepth(root.left, root, depth + 1)
            if root.right != parent:
                getDepth(root.right, root, depth + 1)
            # 向父节点方向递归，比如递归到val=2的节点，不需要像父节点走，如果走的话会重新从5开始
            if pres[root] != parent:
                getDepth(pres[root], root, depth + 1)
        getDepth(target)
        return ans

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func distanceK(root *TreeNode, target *TreeNode, k int) []int {

  var helper func(root *TreeNode, parent *TreeNode)
  pres := map[*TreeNode]*TreeNode{}
  helper = func(root *TreeNode, parent *TreeNode){
      if root == nil{
          return
      }
      pres[root] = parent
      helper(root.Left, root)
      helper(root.Right, root)
  }
  helper(root, nil)
  ans := make([]int, 0)

  var getDepth func(root *TreeNode, parent *TreeNode, depth int)
  getDepth = func(root *TreeNode, parent *TreeNode, depth int){
      if root == nil{
          return
      }
      if depth == k{
          ans = append(ans, root.Val)
      }
      if root.Left != parent{
          getDepth(root.Left, root, depth+1)
      }
      if root.Right != parent{
          getDepth(root.Right, root, depth+1)
      }
      if pres[root] != parent{
          getDepth(pres[root], root, depth+1)
      }
  
  }
  getDepth(target, &TreeNode{}, 0)
  return ans
}

// Make sure to add code blocks to your code group

1.1.11.删点成林 (opens new window)(需要再理解下)

给出二叉树的根节点 root，树上每个节点都有一个不同的值。

如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。

返回森林中的每棵树。你可以按任意顺序组织答案。

示例 1：

输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出：[[1,2,null,4],[6],[7]]

示例 2：

输入：root = [1,2,4,null,3], to_delete = [3]
输出：[[1,2,4]]

# 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 delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        to_delete_set= set(to_delete)
        roots = []
        self.dfs(root, True, to_delete_set, roots)
        return roots

    def dfs(self, node: Optional[TreeNode], is_root: bool, to_delete_set:set[int], roots:List[TreeNode]):
        if node == None:
            return None
        delete = node.val in to_delete_set
        node.left = self.dfs(node.left, delete,to_delete_set, roots)
        node.right = self.dfs(node.right, delete, to_delete_set, roots)
        if delete:
            return None
        else:
            if is_root:
                roots.append(node)
            return node

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func delNodes(root *TreeNode, to_delete []int) []*TreeNode {
  toDeleteSet := make(map[int]bool)
  for _, val := range to_delete {
      toDeleteSet[val] = true
  }
  
  var forest []*TreeNode
  
  var dfs func(node *TreeNode, isRoot bool) *TreeNode
  dfs = func(node *TreeNode, isRoot bool) *TreeNode {
      if node == nil {
          return nil
      }
      
      shouldDelete := toDeleteSet[node.Val]
      
      if isRoot && !shouldDelete {
          forest = append(forest, node)
      }
      
      node.Left = dfs(node.Left, shouldDelete)
      node.Right = dfs(node.Right, shouldDelete)
      
      if shouldDelete {
          return nil
      }
      
      return node
  }
  
  dfs(root, true)
  
  return forest
}

// Make sure to add code blocks to your code group

二叉搜索树

BST特征：中序遍历为单调递增的二叉树，换句话说，根节点的值比左子树任意节点值都大，比右子树任意节点值都小，增删查改均为O（h）复杂度，h为树的高度；注意不是所有的BST题目都需要递归，有的题目只需要while循环即可

笔记

参考前面二叉树下的题型

基于图的DFS

和``BFS一样一般需要一个set来记录访问过的节点，避免重复访问造成死循环; Word XXX 系列面试中非常常见，例如word break，word ladder，word pattern，word search`

1.3.1.扁平化嵌套列表迭代器 (opens new window)

给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。

实现扁平迭代器类 NestedIterator ：

• NestedIterator(List<NestedInteger> nestedList) 用嵌套列表 nestedList 初始化迭代器。
• int next() 返回嵌套列表的下一个整数。
• boolean hasNext() 如果仍然存在待迭代的整数，返回 true ；否则，返回 false 。

你的代码将会用下述伪代码检测：

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

如果 res 与预期的扁平化列表匹配，那么你的代码将会被判为正确。

示例 1：

输入：nestedList = [[1,1],2,[1,1]]
输出：[1,1,2,1,1]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。

示例 2：

输入：nestedList = [1,[4,[6]]]
输出：[1,4,6]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

笔记

嵌套的整型列表是一个树形结构，树上的叶子节点对应一个整数，非叶节点对应一个列表。

在这棵树上深度优先搜索的顺序就是迭代器遍历的顺序。

我们可以先遍历整个嵌套列表，将所有整数存入一个数组，然后遍历该数组从而实现 next 和 hasNext 方法

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def isInteger(self) -> bool:
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        """
#
#    def getInteger(self) -> int:
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        """
#
#    def getList(self) -> [NestedInteger]:
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        """

class NestedIterator:
    def dfs(self, nests):
        for nest in nests:
            if nest.isInteger():
                self.queue.append(nest.getInteger())
            else:
                self.dfs(nest.getList())

    def __init__(self, nestedList: [NestedInteger]):
        self.queue = deque()
        self.dfs(nestedList)
    
    def next(self) -> int:
        return self.queue.popleft()
    
    def hasNext(self) -> bool:
        return len(self.queue)
         

# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* type NestedInteger struct {
* }
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* func (this NestedInteger) IsInteger() bool {}
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* // So before calling this method, you should have a check
* func (this NestedInteger) GetInteger() int {}
*
* // Set this NestedInteger to hold a single integer.
* func (n *NestedInteger) SetInteger(value int) {}
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* func (this *NestedInteger) Add(elem NestedInteger) {}
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The list length is zero if this NestedInteger holds a single integer
* // You can access NestedInteger's List element directly if you want to modify it
* func (this NestedInteger) GetList() []*NestedInteger {}
*/

type NestedIterator struct {
  vals []int
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
  var vals []int
  var dfs func([]*NestedInteger)
  dfs = func(nestedList []*NestedInteger){
      for _, nest := range nestedList{
          if nest.IsInteger(){
              vals = append(vals, nest.GetInteger())
          } else {
              dfs(nest.GetList())
          }
      }
  }
  dfs(nestedList)
  return &NestedIterator{vals}
}


func (this *NestedIterator) Next() int {
  val := this.vals[0]
  this.vals = this.vals[1:]
  return val

}

func (this *NestedIterator) HasNext() bool {
  return len(this.vals) > 0
}

// Make sure to add code blocks to your code group

1.3.2字符串解码 (opens new window)

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

class Solution:
    def decodeString(self, s: str) -> str:

        def dfs(index):
            res, multi = "", 0
            while index < len(s):

                if "0"<=s[index]<="9":
                    multi = multi * 10 + int(s[index])
                elif s[index] == "[":
                    temp, index = dfs(index+1)
                    res += multi * temp
                    multi = 0
                elif s[index] == "]":
                    return res, index
                else:
                    res += s[index]
                index += 1
            return res, index
        return dfs(0)[0]

func decodeString(s string) string {
  res, _ := dfs(s, 0)
  return res
}

func dfs(s string, i int)(res string, index int){

  res, multi := "", 0

  for i < len(s){
      val := s[i]
      if val >= '0' && val <= '9'{
          multi = multi * 10 + int(val - '0')
      } else if val == '['{
          temp, index := dfs(s, i + 1)
          temp = strings.Repeat(temp, multi)
          res += temp
          multi = 0
          i = index
      } else if val == ']'{
          return res, i
      } else{
          res += string(s[i])
      }
      i += 1
  }
  return res, i
}

// Make sure to add code blocks to your code group

1.3.3.N 皇后 (opens new window)

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if not n:
            return []
        board = [["."]*n for _ in range(n)]
        res = []

        def isValid(board, row, col): # 判断这个点是否可以放置n皇后

            # 判断这一列是否满足
            for i in range(n):
                if board[i][col] == "Q":
                    return False
            
            # 判断左上
            i = row -1
            j = col -1
            while i>=0 and j>=0:
                if board[i][j] == "Q":
                    return False
                j -= 1
                i -= 1

            # 判断右上是否满足
            i = row -1
            j = col +1
            while i >=0 and j<n:
                if board[i][j] == "Q":
                    return False
                i -= 1
                j += 1
            return True


        def backtrack(board, row):
            if row==n:
               res.append(["".join(temp) for temp in board[:]])
               return

            for col in range(n):
                if not isValid(board,row, col):
                    continue
                board[row][col] = "Q"
                backtrack(board, row+1)
                board[row][col] = "."
        backtrack(board, 0)
        return res  

func solveNQueens(n int) [][]string {
  /* 
  主函数处理边界问题，调用回溯函数
  回溯函数进行回溯，查找不同结果，在每个位置判断
  该点是否可以放置Q
  定义判断函数，通过比对该位置的列，左上，右上位置来确定是否满足题意
  通过判断当前位置是否满足
  */

  res := [][]string{}
  board := make([][]string, n)

  // 初始化棋盘
  for i:=0;i<n;i++{
      board[i]= make([]string, n)
      for j := range board[i]{
          board[i][j] = "."
      }
  }
  backtrack(&res, board, 0, n)
  return res
}


func backtrack(res *[][]string, board [][]string, row int, n int){
  if row == n{
      temp := make([]string, n)
      //[[.... Q...], [..... Q ...]]]
      for i:=0;i<n;i++{
          ch := strings.Join(board[i], "")
          temp[i] = ch
      }
      *res = append(*res, temp)
      return
  }

  for col:=0;col<n;col++{
      if !isValid(board, row, col){
          continue
      }
      board[row][col] = "Q"
      backtrack(res, board, row+1, n)
      board[row][col] = "."

  }        
}


func isValid(board [][]string , row int, col int) bool{
  // 先判断这一列是否符合条件
  
  for i:=0;i<len(board);i++{
      if board[i][col] == "Q"{
          return false
      }
  }
  // 左上
  i := row -1
  j := col -1
  for i>=0 && j>=0{
      if board[i][j] == "Q"{
          return false
      }
      i -= 1
      j -= 1
  }
  // 右上
  r := row -1
  c := col +1
  for r>=0 && c<len(board){
      if (board[r][c]) == "Q"{
          return false 
      }
      r -= 1
      c += 1
  }
  return true
}

// Make sure to add code blocks to your code group

1.3.4.复原 IP 地址 (opens new window)

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和"192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        """
        回溯算法
        """
        ret = list()
        path = list()

        def backtracking(startindex, path):
            if len(path) == 4 and startindex == len(s):
                ret.append(".".join(path[:]))
                return
            
            if startindex >= len(s):
                return
            
            if len(path) >=4:
                return 
            if s[startindex] == "0":
                path.append("0")
                backtracking(startindex+1, path)
                path.pop()
            for i in range(startindex, len(s)):
                end = i + 1
                seg = int(s[startindex:end])
                if 0<seg<=255:
                    path.append(str(seg))
                    backtracking(i+1, path)
                    path.pop()
                else:
                    break
        backtracking(0, path)
        return ret

func restoreIpAddresses(s string) []string {

  res := make([]string, 0)
  path := make([]string, 0)

  var backtracking func(path []string, start int)
  backtracking = func(path []string, start int){
      if len(path) == 4 && start == len(s){
          temp := make([]string, len(path))
          copy(temp, path)
          res = append(res, strings.Join(temp, "."))
          return
      }
      if start == len(s){
          return
      }
      if s[start] == '0'{
          path = append(path, "0")
          backtracking(path, start + 1)
          path = path[:len(path)-1]
      }
      for i:= start;i<len(s);i++{
          end := i + 1
          seg, _ := strconv.Atoi(s[start:end])
          if seg >0 && seg <= 255{
              path = append(path, strconv.Itoa(seg))
              backtracking(path, end)
              path = path[:len(path)-1]
          } else{
              break
          }
      }
  }
  backtracking(path, 0)
  return res
}

// Make sure to add code blocks to your code group

1.3.5括号生成 (opens new window)

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示

我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，

如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = list()

        def backtrack(s, left, right):
            if len(s) == 2*n:
                ans.append("".join(s))
            
            if left <n:
                s.append("(")
                backtrack(s, left +1, right)
                s.pop()
            if right < left:
                s.append(")")
                backtrack(s, left, right+1)
                s.pop()
        backtrack([], 0, 0)
        return ans

func generateParenthesis(n int) []string {
  // var path string
  ret :=[]string{}
  var backtracking func(string, int, int)
  backtracking = func (path string, left , right int){
      if len(path) == 2*n{
          ret = append(ret, path)
          return
      }

      if left < n{
          // path = append(path, "(")
          backtracking(path + "(", left+1, right) // 这里是隐式的回溯，由于传递的是path + "("， 所以其实path 这个变量的值是没有变的，所以省去了pop的操作
          // path.pop()
      }
      if right < left{
          backtracking(path + ")", left, right +1)
      }
  }
  backtracking("", 0, 0)
  return ret
}

// Make sure to add code blocks to your code group

1.3.6.括号的分数 (opens new window)

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

• () 得 1 分。
• AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
• (A) 得 2 * A 分，其中 A 是平衡括号字符串。

示例 1：

输入： "()"
输出： 1

示例 2：

输入： "(())"
输出： 2

示例 3：

输入： "()()"
输出： 2

示例 4：

输入： "(()(()))"
输出： 6

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        n = len(s)
        if n == 2:
            return 1
        bal = 0
        for i, c in enumerate(s):
            bal += 1 if c == '(' else -1
            if bal == 0:
                if i == n - 1:
                    return 2 * self.scoreOfParentheses(s[1:-1])
                return self.scoreOfParentheses(s[:i + 1]) + self.scoreOfParentheses(s[i + 1:])

func scoreOfParentheses(s string) int {
  n := len(s)
  if n == 2 {
      return 1
  }
  for i, bal := 0, 0; ; i++ {
      if s[i] == '(' {
          bal++
      } else {
          bal--
          if bal == 0 {
              if i == n-1 {
                  return 2 * scoreOfParentheses(s[1:n-1])
              }
              return scoreOfParentheses(s[:i+1]) + scoreOfParentheses(s[i+1:])
          }
      }
  }
}

// Make sure to add code blocks to your code group

1.3.7.通知所有员工所需的时间 (opens new window)

公司里有 n 名员工，每个员工的 ID 都是独一无二的，编号从 0 到 n - 1。公司的总负责人通过 headID 进行标识。

在 manager 数组中，每个员工都有一个直属负责人，其中 manager[i] 是第 i 名员工的直属负责人。对于总负责人，manager[headID] = -1。题目保证从属关系可以用树结构显示。

公司总负责人想要向公司所有员工通告一条紧急消息。他将会首先通知他的直属下属们，然后由这些下属通知他们的下属，直到所有的员工都得知这条紧急消息。

第 i 名员工需要 informTime[i] 分钟来通知它的所有直属下属（也就是说在 informTime[i] 分钟后，他的所有直属下属都可以开始传播这一消息）。

返回通知所有员工这一紧急消息所需要的 分钟数 。

示例 1：

输入：n = 1, headID = 0, manager = [-1], informTime = [0]
输出：0
解释：公司总负责人是该公司的唯一一名员工。

示例 2：

输入：n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
输出：1
解释：id = 2 的员工是公司的总负责人，也是其他所有员工的直属负责人，他需要 1 分钟来通知所有员工。
上图显示了公司员工的树结构。

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        g = [[] for _ in range(n)]
        for i, m in enumerate(manager):
            if m >= 0:
                g[m].append(i)
        
        def dfs(x:int) -> int:
            max_path_sum = 0
            for y in g[x]:
                max_path_sum = max(max_path_sum, dfs(y))
            return max_path_sum + informTime[x]
        return dfs(headID)

// Make sure to add code blocks to your code group

1.3.8.分割回文串 (opens new window)

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是

回文串

。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

class Solution:
    def partition(self, s: str) -> List[List[str]]:

        res = list()
        path = list()

        def backtracking(path, start):
            if start == len(s):
                res.append(path[:])
                return
            for i in range(start, len(s)):
                temp = s[start:i+1]

                if temp == temp[::-1]:
                    # path.append(temp)
                    backtracking(path+[temp], i+1)
                    # path.pop()

        backtracking(path, 0)
        return res

// Make sure to add code blocks to your code group

基于排列组合的DFS

其实与图类DFS方法一致，但是排列组合的特征更明显