跳至内容
全部笔记
Tree_search

Tree_search

Tree Search

目录结构

----
一、翻转树二、相同树三、层序遍历并标序四、对称树
五、二叉树的最大深度六、二叉树的最小深度七、路径总和八、二叉树层序遍历无标序号
九、岛屿的周长十、左叶子之和十一、二叉搜索树的最小绝对差十二、二叉树层序遍历II
十三、合并二叉树十四、二叉树的层平均值十五、找出克隆二叉树中的相同节点十六、图像渲染
[十七、N叉树的最大深度](#十七N 叉树的最大深度)十八、单值二叉树十九、二叉树的堂兄弟节点二十、寻找图中是否存在路径
二十一、另一棵树的子树二十二、二叉树中第二小的节点二十三、二叉搜索树中的众数二十四、表格里单词搜索
二十五、二叉树化单链表二十六、找到所有的农场组[二十七、路径总和 II](#二十七路径总和 II)二十八、二叉树展开为链表

队列的运用：一、二、

一、翻转树

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 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]:
        # 排除root为空的情况
        if not root:
            return root
        # 队列 <——> list
        que=[root]		
        
        # 循环条件：队列不为空
        while que:
            # 出队
            tnode=que.pop(0)
            
            # 如果左子树存在，入队
            if tnode.left:
                que.append(tnode.left)
                
            # 如果右子树存在，入队
            if tnode.right:
                que.append(tnode.right)
                
            # 将开头出队的左右子树换位
            a=tnode.right
            tnode.right=tnode.left
            tnode.left=a
        return root
    #关键在于，队列初始化、出入队操作，以及存在才入队。

二、相同树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 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: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        p_ls=[p]
        q_ls=[q]
        
        while(p_ls):
            p_n=p_ls.pop(0)
            q_n=q_ls.pop(0)

            if (p_n is None and q_n is not None or q_n is None and p_n is not None):
                return False

            if p_n and q_n:
                if p_n.val!=q_n.val:
                    return False

                p_ls.append(p_n.left)
                p_ls.append(p_n.right)
                q_ls.append(q_n.left)
                q_ls.append(q_n.right)

        return True

三、层序遍历并标序（自定义）（通解性）

此题为自定义的，具有通解性质，可暴力解决很多题目。

给你一个二叉树的根节点 root ，一层一层地打印并标明位置，包括空结点。

关键是通过上层序号，向左子树走+0，向右子树走+1

打印类似：

(root,0)

(left,0) (right,1)

(left_left,0) (left_right,1) (none,2) (right_right,3)

(?,0) (?,1) (?,2) (?,3) (?,6) (?,7)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# 在 104. 二叉树的最大深度 测试的
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        que=[(root,0)]
        while que:
            for _ in range(len(que)):
                tnode, pos=que.pop(0)
                print(f"{tnode.val if tnode else None},{pos}\t", end='')
                if tnode:
                    que.append((tnode.left,pos*2))
                    que.append((tnode.right,pos*2+1))
            print()

四、对称树

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

# 暴力标出行点位
# 变量说明
# q: que 队列		cnt: 记录某层存在的结点的个数	n_lay: 当前层总位置数，即2^k个，k=0,1,2...
# n: 当前层未分析的结点个数，初始为cnt，然后-1-1-1...
# cp_cnt: 记录当前层的结点总个数，初始和n一样，只不过不会变化
# stack: 栈，进栈一半结点后，开始分析对称性时，通过出栈互消除
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    	if not root:
            return True
        
        q=[(root,0)]	# 队列
        cnt=1   # 初始化第一层要分析的结点数
        n_lay=1     # 当前层的位置总个数
        while(q):
            n=cnt   # 该层 还要 分析结点数，不停地减一
            cp_cnt=cnt  # 该层 结点总数
            cnt=0   # 清零保存下层结点数
            stack=[]
            # 遍历当前层
            while (n):

                tnode=q.pop(0) 

                if n<=cp_cnt/2:
                    # 出栈
                    pop_node=stack.pop(-1)

                    # 都是真，核对位置和值
                    if tnode[0] and pop_node[0]:
                        if tnode[0].val!=pop_node[0].val:
                            print('A')
                            return False     
                        if (tnode[1]+pop_node[1])!=n_lay-1:
                            print('B')
                            return False    
                    # 排除了都是真，但不都None，则必为一真一None
                    elif tnode[0] or pop_node[0]:
                        print('C')
                        return False 
                    else:
                        # 都是None，核对位置
                        if (tnode[1]+pop_node[1])!=n_lay-1:
                            print('D')
                            return False            
                                           
                    # 都是None则已经出栈完成互消
                else:
                    stack.append(tnode)

                if tnode[0]:
                    q.append((tnode[0].left,tnode[1]*2+0))
                    q.append((tnode[0].right,tnode[1]*2+1))
                    cnt+=2
                    
                n-=1

            n_lay*=2
             
        return True        
1
2
3
4
5
6
7
8
9

# 递归
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)

五、二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）

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

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

两种思路：自顶向下 和 自底向上

  • 自顶向下：顶层为1，向下加一并取最大返回
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# 自顶向下
class Solution:
    def recur(self,tnode:Optional[TreeNode],dep:int)->int:
        if not tnode:
            return dep-1
        else:
            return max(self.recur(tnode.left, dep+1),
                    self.recur(tnode.right, dep+1))
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.recur(root,1)
  • 自底向上：最底空结点为0，一直向上加，太惊艳了

“我在网上看到一种理解递归的说法：「在写递归函数时，可以假设递归返回的结果一定是正确的」。其实这种说法本质上就是数学归纳法。”——作者

代码中 max(l_depth, r_depth) + 1 就是假设l_depth 和 r_depth是正确的，然后本层则为 max(l_depth, r_depth) + 1

​ if root is None: ​ return 0 ​ l_depth = self.maxDepth(root.left) ​ r_depth = self.maxDepth(root.right) 则保证了初始状况也是正确的，刚才的假设便成立，就能得到正确结果。

https://leetcode.cn/problems/maximum-depth-of-binary-tree/solutions/2010612/kan-wan-zhe-ge-shi-pin-rang-ni-dui-di-gu-44uz/

1
2
3
4
5
6

# 自底向上
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

六、二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

111. 二叉树的最小深度 - 力扣（LeetCode）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 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 minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        # root此时必为True
        return self.recur(root)
    def recur(self, root: Optional[TreeNode]) -> int:
        # 俩子节点都为False
        if not (root.left or root.right):
            return 1
        # 俩子节点都为True
        elif root.left and root.right:
            return min(self.recur(root.left),self.recur(root.right))+1
        # 1 True 1 False
        else:
            return self.recur(root.left)+1 if root.left else self.recur(root.right)+1

七、路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

112. 路径总和 - 力扣（LeetCode）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

# 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

        def dfs(node, target, s):
            if not node:return False
            s+=node.val
            if not node.left and not node.right:
                if s==target:
                    return True
                else:
                    return False
            return dfs(node.left, target, s) or dfs(node.right, target, s)
            
        return dfs(root, targetSum, 0)

八、二叉树层序遍历无标序号

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

“三、层序遍历并标序”的简单版。

102. 二叉树的层序遍历 - 力扣（LeetCode）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 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]]:
        # 保证root有val
        if not root:
            return []
        q=[root]
        nodes=[]
        # 全部遍历（相对层内而言）
        while(q):
            tmp=[]
            # 层内遍历
            for _ in range(len(q)):
                tnode=q.pop(0)
                tmp.append(tnode.val)
                if(tnode.left):
                    q.append(tnode.left)
                if(tnode.right):
                    q.append(tnode.right)
            nodes.append(tmp)
        return nodes

九、岛屿的周长

岛屿的周长

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

1
2
3

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

# 不用检查每个土格四周是否也是土格子，因为a格子右边是b格子，
# 则b格子左边必然是a格子，只需检查每个格子的左上即可
class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        # 定义行数、列数和周长
        row=len(grid)
        col=len(grid[0])
        sum=0
        # row_ls: row list			e: element
        for i,row_ls in enumerate(grid):
            for j,e in enumerate(row_ls):
                # 如果是地
                if e:
                    sum+=4
                    # 检查左方格是否为土，首先排除向左超边界
                    if j!=0 and grid[i][j-1]:
                        sum-=2
                    # 检查上方格是否为土，首先排除向上超边界
                    if i!=0 and grid[i-1][j]:
                        sum-=2
        return sum

十、左叶子之和

404. 左叶子之和 - 力扣（LeetCode）

给定二叉树的根节点 root ，返回所有左叶子之和。

1
2
3

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

# 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 sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        l_c=root.left
        r_c=root.right
        l_cnt=r_cnt=0
        if l_c:
            if not l_c.left and not l_c.right:
                l_cnt+=l_c.val
            else:
                l_cnt=self.sumOfLeftLeaves(l_c)
        # 右孩子非空且非叶子结点
        if r_c and r_c.left or r_c.right:
                r_cnt=self.sumOfLeftLeaves(r_c)
        return l_cnt+r_cnt

十一、二叉搜索树的最小绝对差

530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

What I learn:

  • 类里的全局变量——类属性（见 十九 ，嵌套函数里声明外部变量 nonelocal）
  • 调用类的属性、方法都要“self.” “self.” “self.” !!!
  • 二叉搜索树 — 中序遍历可得由小到大的序列，其他题见 二十三、二叉搜索树中的众数
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 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 __init__(self):
        self.dif=inf
        self.pre=-inf
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:

        if root.left:
            self.getMinimumDifference(root.left)

        self.dif=min(self.dif, root.val-self.pre)

        self.pre=root.val

        if root.right:
            self.getMinimumDifference(root.right)

        return self.dif

十二、二叉树层序遍历II

107. 二叉树的层序遍历 II - 力扣（LeetCode）

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 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 []
        q=[root]
        nodes=[]
        while(q):
            tmp=[]
            for _ in range(len(q)):
                tnode=q.pop(0)
                tmp.append(tnode.val)
                if tnode.left:
                    q.append(tnode.left)
                if tnode.right:
                    q.append(tnode.right)
            nodes.append(tmp)
        return nodes[::-1]

十三、合并二叉树

617. 合并二叉树 - 力扣（LeetCode）

**递归：1. 假定往下传一些参数，他能返回理想值，2. 当前层，接收了上层参数，确保能返回理想值。**具体看代码注释，关键是 “处理好当前层内容，正确返回上层”

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        # ===== 当前层，接收了上层参数，确保能返回理想值 =====
        # 都为空传回空
        if root1 is None and root2 is None:
            return None
        # 否则必有一个非空
        # 一个非空传回 非空那个
        if root1 is None:
            return root2
        if root2 is None:
            return root1
        # 否则必然都非空
        # 都非空，不return，加和当前结点值，继续往下执行
        root1.val+=root2.val
        
        # ===== 假定往下传一些参数，他能返回理想值 =====
       	root1.left=self.mergeTrees(root1.left,root2.left)
        root1.right=self.mergeTrees(root1.right,root2.right)
        
       	return root1

十四、二叉树的层平均值

637. 二叉树的层平均值 - 力扣（LeetCode）

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        if not root:
            return []
        q=[root]
        ave=[]
        while(q):
            tmp=0.0		    #当前层的和
            q_len=len(q)	# 当前层长度
            for _ in range(q_len):
                tnode=q.pop(0)
                tmp+=tnode.val
                if tnode.left:
                    q.append(tnode.left)
                if tnode.right:
                    q.append(tnode.right)
            ave.append(tmp/q_len)

        return ave

十五、找出克隆二叉树中的相同节点

1379. 找出克隆二叉树中的相同节点 - 力扣（LeetCode）

给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。

其中，克隆树 cloned 是原始树 original 的一个 副本 。

请找出在树 cloned 中，与 target 相同 的节点，并返回对该节点的引用（在 C/C++ 等有指针的语言中返回 节点指针，其他语言返回节点本身）。

What I have leaned:

  • 声明全局变量 未必比 传形参要好，因为python都是传引用，除非对其修改 才可能 创建副本
  • TreeNode可以直接进行比较，实际比较的是 物理内存地址（指针），target和original指到同一处时，original is target才为True，cloned is target永远为False
1
2
3
4
5
6
7
8

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        if original is None or original is target:
            return cloned
        return self.getTargetCopy(original.left, cloned.left, target) or \
               self.getTargetCopy(original.right, cloned.right, target)

作者：灵茶山艾府

十六、图像渲染

733. 图像渲染 - 力扣（LeetCode）

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数 sr , sc 和 color 。你应该从像素 image[sr][sc] 开始对图像进行上色 填充 。

为了完成 上色工作：

  1. 从初始像素开始，将其颜色改为 color。
  2. 对初始坐标的 上下左右四个方向上 相邻且与初始像素的原始颜色同色的像素点执行相同操作。
  3. 通过检查与初始像素的原始颜色相同的相邻像素并修改其颜色来继续 重复 此过程。
  4. 当 没有 其它原始颜色的相邻像素时 停止 操作。

最后返回经过上色渲染 修改 后的图像 。

what you learn:

  • 初始像素与目标颜色相同。不会对图像进行任何更改。
  • 找一种中序遍历的感觉
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        q=[(sr,sc)]
        r_len=len(image)
        c_len=len(image[0])
        # original color
        ori_c=image[sr][sc]
        if ori_c==color: return image
        while(q):
            # element
            e=q.pop(0)
            # current block's color
            image[e[0]][e[1]]=color
            # 上:行不为0
            if e[0] and image[e[0]-1][e[1]] == ori_c:
                q.append((e[0]-1, e[1]))
            # 左：列不为0
            if e[1] and image[e[0]][e[1]-1] == ori_c:
                q.append((e[0], e[1]-1))

            # 下：行不为r_len-1
            if e[0]!=r_len-1 and image[e[0]+1][e[1]] == ori_c:
                q.append((e[0]+1, e[1]))

            # 右：列不为c_len-1
            if e[1]!=c_len-1 and image[e[0]][e[1]+1] == ori_c:
                q.append((e[0], e[1]+1))

        return image

十七、N 叉树的最大深度

559. N 叉树的最大深度 - 力扣（LeetCode）

给定一个 N 叉树，找到其最大深度。

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

What I learn:

  • 不要掉入惯性思维的坑，仔细看它定义的类（结构体）是怎样的，此题没有空结点（对比 二叉树最大深度 的 定义，它不是子树结点为None而是存子树的list为None，因此，无法实现 “当前结点为None”这种做法。
  • 这就引出在递归结尾处的两种处理，一种是“如果子树不为空，才进入递归函数”，另一种是“子树结点传进递归函数，函数开头判断是否为空”，我称前者为“预判处理”，后者为“当前层处理”。二者看情况用，通常用“当前层处理”，但这里不行，因为没有 空结点。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, 
    children: Optional[List['Node']] = None):
        self.val = val
        self.children = children
"""

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            # 注意函数返回值限制为int类型
            return 0
        # 注意不是从空结点层向上返回的，故不是从0开始
        return \
        max([self.maxDepth(node) for node in root.children])+1 \
        if root.children else 1

十八、单值二叉树

965. 单值二叉树 - 力扣（LeetCode）

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

What I learn:

  • 方法里定义的临时变量（代码里的 v ），对于方法里的函数（哪怕递归了）是全局的。

    —— 当dfs被定义为嵌套函数时，它可以访问外部函数isUnivalTree中的变量v（闭包机制）

    —— 如果将dfs改为实例方法（如self.dfs），不能访问外部函数的变量v

    —— 还要看是访问的变量类型，不可变类型：可读，要写需nonlocal；

    ​ 可变类型：可读可写

  • 如果有多个、多重if else，看看能不能用 or and 代替

  • 定义参数时不要和外边变量重名，如：def dfs(node): 而非 def dfs(root):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 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 isUnivalTree(self, root: TreeNode) -> bool:
        # 变量v对于dfs是全局的
        v = root.val
        def dfs(node):
            return node is None or \
            (node.val == v and dfs(node.left) and dfs(node.right))
        
        return dfs(root)

作者：Benhao

''' 
return node is None or \
        (node.val == v and dfs(node.left) and dfs(node.right))

===== 等价于 =====

if not root:
	return True

if root.val==self.n:
	return self.recur(root.left) and self.recur(root.right)
else:
	return False
'''

十九、二叉树的堂兄弟节点

993. 二叉树的堂兄弟节点 - 力扣（LeetCode）

在二叉树中，两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。

What I learn:

  • 当你想得清楚当前层的处理时，发现要上层数据，想想能不能传递上层数据下去

  • 嵌套函数 对 外部作用域变量的访问 的关键区别：读取和修改。

    只要函数内部存在对不可变类型变量 pre_dep 的 修改（如 pre_dep = dep），Python 默认将其视为 局部变量。

    仅读取，则会视为外部变量（见 十八 的 v）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 当你想得清楚当前层的处理时，发现要上层数据，想想能不能传递上层数据下去
class Solution:

    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        if root.val==x or root.val==y:
            return False
        
        pre_dep=0
        pre_par=None

        def recur(root, dep, par):
            nonlocal pre_dep, pre_par
            if not root:
                return False
            # 如果有一个值对上了，说明遇上了一个结点
            if root.val==x or root.val==y:
                # 如果pre_dep不为0，前者已找到，必须深度一样且父节点不同
                if pre_dep:
                    return dep==pre_dep and par is not pre_par
                else:
                    pre_dep=dep
                    pre_par=par
                    
            return recur(root.left, dep+1, root) or\
                recur(root.right, dep+1, root)

        return recur(root.left, 1, root) or \
               recur(root.right, 1, root)

二十、寻找图中是否存在路径

1971. 寻找图中是否存在路径 - 力扣（LeetCode）

有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。

存在 有效路径 ，则返回 true，否则返回 false 。

1
2

输入：n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
输出：true

What I learn:

  • defaultdict(list)将“边数据”转为“点数据”，复杂度由 n^2 变 n，边=n(n-1)/2=n^2
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        def dfs(i):
            if i == destination:
                return True
            vis.add(i)
            for j in g[i]:
                if j not in vis and dfs(j):
                    return True
            return False

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        vis = set()
        return dfs(source)

作者：ylb

二十一、另一棵树的子树

572. 另一棵树的子树 - 力扣（LeetCode）

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

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

What I learn:

  • 探索必要条件：如果是子树，那就有相同树，则二者深度必然相等，也就是深度相等的结点才需判断是不是相同树。 此必要条件能大幅减小复杂度。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

# 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 check(node1,node2):
            if node1 is None and node2 is None:
                return True
            elif node1 and node2:
                if node1.val==node2.val:
                    return check(node1.left, node2.left) and check(node1.right, node2.right)
            return False

        # 排除根节点为空的情况
        if not subRoot:
            return True
        elif not root:
            return False
        
        # 计算子树深度
        def cal_sub(node):
            if not node:
                return 0
            return max(cal_sub(node.left),cal_sub(node.right))+1
        sub_dep=cal_sub(subRoot)
        # 子树根节点值
        sub_v=subRoot.val

        # 遍历树，深度相同 且 值相同 时检查
        def dfs(node)->(int, bool):
            if not node:
                return 0, False
            l_dep, l_issub = dfs(node.left)
            r_dep, r_issub = dfs(node.right)
            
            dep=max(l_dep,r_dep)+1
            if l_issub or r_issub:
                return 0, True
            
            if dep==sub_dep and node.val==sub_v:
                if check(node,subRoot):
                    return 0, True
            
            return dep, False

        return dfs(root)[1]

二十二、二叉树中第二小的节点

671. 二叉树中第二小的节点 - 力扣（LeetCode）

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。

更正式地说，即 root.val = min(root.left.val, root.right.val) 总成立。

给出这样的一个二叉树，你需要输出所有节点中的 第二小的值 。

如果第二小的值不存在的话，输出 -1 。

1
2
3

输入：root = [2,2,5,null,null,5,7]
输出：5
解释：最小的值是 2 ，第二小的值是 5 。

What I learn

  • 假设递归终点正确返回，处理中间过程：

    我们知道root.val是最小值，那么

    第二小的值为 较小的子节点那一边的子树的第二小的值 或 更大的子节点 之中

    即min(get_sec_min(较小结点), 较大结点.val)

    因为当前层是考虑了子节点的，所以是“预判式递归”

  • 处理末尾情况，使“数学归纳法”成立：

    “预判式递归”考虑倒数两层，1. 最底一层因为有空叶子而需要特殊处理。2. 倒数第二层（中间过程）要看看最底一层的返回是否兼容（即min(get_sec_min(较小结点), 较大结点.val)是否合理）

    这里就是：

    ​ child有返回-1时要取max，或者

    新写一个函数，叶子返回inf，外部再处理返回inf的情况。

  • “限制性递归”就不是每个子节点都进入，需要“预判处理”，见 [十七、N叉树的最大深度](#十七N 叉树的最大深度)

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

    # 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:
        # 会从沿着值为root.val的路线往下走，总共考虑 是/否为叶子、较大/较小子树方向
        # 如果当前是值为root.val的叶子返回-1，如果当前是值为不为root.val的叶子的情况不存在   
        def findSecondMinimumValue(self, root: TreeNode) -> int:
            # 必然不存在第二小的值
            if not root or not root.left:
                return -1
            # 我们知道root.val是最小值，那么
            # 第二小的值存在于 更小的子节点那一边的子树的第二小的值 或 更大的子节点 之中
            left = root.left.val if root.left.val != root.val \
              else self.findSecondMinimumValue(root.left)
            right = root.right.val if root.right.val != root.val \
              else self.findSecondMinimumValue(root.right)

            return min(left, right) if left != -1 and right != -1 else max(left, right)

二十三、二叉搜索树中的众数

501. 二叉搜索树中的众数 - 力扣（LeetCode）

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

What the hell did I learn:

  • 二叉搜索树 — 中序遍历可得由小到大的序列，相当于将树拍平在数轴上，

    如 1, 2, 2, 4, 6, 6, 9，递归每层相当于指针指到某处

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# 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

# 左->当前->右
# v=[]  v_n=0  n_max=0 pre=前一结点值，初始inf则都不相等
class Solution:
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        pre=inf
        v=[]
        v_n=0
        n_max=0

        def dfs(node):
            if not node:
                return
            dfs(node.left)
            
            nonlocal v_n, pre, n_max
		   
            # 与前一值的关系，等则累加，不等则置1
            if node.val!=pre:
                pre=node.val
                v_n = 1
            else:
                v_n += 1

            # 个数情况，小于最大值不处理
            if v_n<n_max:
                None
            elif v_n==n_max:
                v.append(node.val)
            else:
                n_max=v_n
                v.clear()
                v.append(node.val)
            
            dfs(node.right)
            
        dfs(root)
        return v

二十四、表格里单词搜索

79. 单词搜索 - 力扣（LeetCode）

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

1
2

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

What I learn:

  • 变量作用域和函数传参总结：

    1. 函数传参传 指针/别名，一定是。
    2. 对于外部不可修改变量：
      • 若传参了
        • 函数内若修改变量，复制生成局部变量，不影响外部变量，读取读局部变量。
        • 函数内若只读取变量，不生成局部变量，指针方式读。
      • 若没传参
        • 函数内若修改变量，报错不存在该局部变量。
        • 函数内若只读取变量，自动指针方式读外部变量。
    3. 对于外部可修改变量：
      • 无论传没传参，修不修改，一律别名方式读取或修改外部变量。

  • 树型标表示

        graph TD
    A[外部变量] --> B[不可修改变量]
    A --> C[可修改变量]

    B --> D[传参]
    B --> E[不传参]

    D --> F[（函数内）修改变量]
    D --> G[只读变量]
    F --> F1[复制生成局部变量]
    G --> G1[指针方式读外部变量]

    E --> H[函数内修改变量]
    E --> I[函数内只读变量]
    H --> H1[报错：不存在该局部变量]
    I --> I1[指针方式读外部变量]

    C --> J[无论传参与否]
    J --> K[无论修改与否]
    K --> L[别名方式读取或修改外部变量]
    1. 不可改-传参-修改-复制生成局部变量
    2. 不可改-传参-只读-指针方式读
    3. 不可改-不传参-修改-报错
    4. 不可改-不传参-只读-指针方式读
    5. 可改 - 传参/不传参 - 修改/不修改 - 别名方式

  • 遍历各方向 并 进入各方向的递归函数：

    1
2
3
4

    # 相邻格子
for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):
    if 0 <= x < m and 0 <= y < n and dfs(x, y, k + 1):
        return True

  • 注意这题里 由于访问可修改变量，一定是别名访问，需要“恢复现场”，即回溯

  • any 是否存在True all 是否都为True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        def dfs(i: int, j: int, k: int) -> bool:
            if board[i][j] != word[k]:  # 匹配失败
                return False
            if k == len(word) - 1:  # 匹配成功！
                return True
            board[i][j] = ''  # 标记访问过
            for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):  # 相邻格子
                if 0 <= x < m and 0 <= y < n and dfs(x, y, k + 1):
                    return True  # 搜到了！
            board[i][j] = word[k]  # 恢复现场
            return False  # 没搜到
        return any(dfs(i, j, 0) for i in range(m) for j in range(n))

作者：灵茶山艾府

二十五、二叉树化单链表

面试题 17.12. BiNode - 力扣（LeetCode）

二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

What I learn:

  • 创建单链表思想：设置头结点，pre初始=头结点，创建当前结点，pre内指针 指向 当前结点，pre=当前结点
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 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 convertBiNode(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        ini_node=TreeNode()
        pre=ini_node
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            
            nonlocal pre
            pre.right=node
            node.left=None
            pre=node

            dfs(node.right)
        dfs(root)
        return ini_node.right

二十六、找到所有的农场组

1992. 找到所有的农场组 - 力扣（LeetCode）

给你一个下标从 0 开始，大小为 m x n 的二进制矩阵 land ，其中 0 表示一单位的森林土地，1 表示一单位的农场土地。

为了让农场保持有序，农场土地之间以矩形的 农场组 的形式存在。每一个农场组都 仅 包含农场土地。且题目保证不会有两个农场组相邻，也就是说一个农场组中的任何一块土地都 不会 与另一个农场组的任何一块土地在四个方向上相邻。

land 可以用坐标系统表示，其中 land 左上角坐标为 (0, 0) ，右下角坐标为 (m-1, n-1) 。请你找到所有 农场组 最左上角和最右下角的坐标。一个左上角坐标为 (r1, c1) 且右下角坐标为 (r2, c2) 的 农场组 用长度为 4 的数组 [r1, c1, r2, c2] 表示。

请你返回一个二维数组，它包含若干个长度为 4 的子数组，每个子数组表示 land 中的一个 农场组 。如果没有任何农场组，请你返回一个空数组。可以以 任意顺序 返回所有农场组。

1
2

输入：land = [[1,0,0],[0,1,1],[0,1,1]]
输出：[[0,0,0,0],[1,1,2,2]]

what I learn:

  • 试探性 行为"x1+1" “y1+1”,不满足则x1 y1抵达边界
  • 多变量时，分清楚“域内变量”是什么？
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        result=[]
        m=len(land)
        n=len(land[0])
		
        # 检测从此出发的矩形有多大
        def check(x0,y0,x1,y1):
            # 试探性 行为"x1+1" "y1+1",不满足则x1 y1抵达边界
            while(x1+1<m and land[x1+1][y1]):
                x1+=1
            while(y1+1<n and land[x1][y1+1]):
                y1+=1
            for i in range(x0,x1+1):
                for j in range(y0,y1+1):
                    land[i][j]=0 
            return (x0,y0,x1,y1)

        # 遍历所有点
        for i in range(m):
            for j in range(n):
                if land[i][j]==1:
                    result.append(check(i,j,i,j))

        return result

二十七、路径总和 II

113. 路径总和 II - 力扣（LeetCode）

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 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]]:
        result=[]

        def dfs(node,Sum,targetSum,route):
            if not node:
                return
            route.append(node.val)
            Sum+=node.val
            if Sum==targetSum and node.left is None and node.right is None:
                result.append(deepcopy(route))
            dfs(node.left,Sum,targetSum,route)
            dfs(node.right,Sum,targetSum,route)
            route.pop(-1)
        
        dfs(root,0,targetSum,[])
        return result

what I learn:

  • python里的 可修改变量 和 不可修改变量 的赋值，可修改-创建新变量，不可修改-别名
1
2
3
4
5
6
7
8
9

ls=[1,2,3]
cp=ls
cp.append(4)
print(ls) # [1,2,3,4]

a=1
cp=a
cp=2
print(a) # 1
  • copy.deepcopy实现 不可修改变量的 “创建变量赋值”
1
2
3
4
5

ls=[1,2,3]
import copy
cp=copy.deepcopy(ls)
cp.append(4)
print(ls) # [1,2,3,4]

二十八、二叉树展开为链表

114. 二叉树展开为链表 - 力扣（LeetCode）

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# 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 flatten(self, root: Optional[TreeNode]) -> None:
        
        # 尾插法
        
        # ini_node=TreeNode()
        # pre=ini_node
        # def dfs(node):
        #     if not node:
        #         return
        #     nonlocal pre
        #     pre.right=node
        #     lc, rc=node.left, node.right
        #     node.left=None
        #     pre=node
        #     dfs(lc)
        #     dfs(rc)
        # dfs(root)

        # 头插法
        
        ini_node=TreeNode()
        def dfs(node):
            if not node:
                return 
            dfs(node.right)
            dfs(node.left)
            nonlocal ini_node
            node.right=ini_node.right
            ini_node.right=node
            node.left=None

        dfs(root)

what I learn:

  • 二叉树先序、中序、后续遍历转二叉树总结：中序-尾插法-LCR处理，后序-尾插法-LRC处理，先序-头插法-RLC处理

    原理：确保 pre的右子树的处理 不会影响后续结点的访问，确保 cur的左子树的处理 不会影响后续结点的访问。

    L(进入left-child) C(处理current) R(进入right-child)

    • 中序-尾插法-LCR，即搜索二叉树遍历。
    1
2
3
4
5

    dfs(node.left)
pre.right=node
node.left=None
pre=node
dfs(node.right)
    • 后序-尾插法-LRC
    1
2
3
4
5

    dfs(node.left)
dfs(node.right)
pre.right=node
node.left=None
pre=node
    • 先序-头插法-RLC 头插法实现将CLR转换为RLC，类后序，当前层处理不会影响后续 向父节点的 访问。
    1
2
3
4
5

    dfs(node.right)
dfs(node.left)
node.right=head.right
head.right=node
node.left=None
最后更新于
文件读写Typora_tricks