基本框架
以dfs求深度为例：
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution : def maxDepth (self , root ): def depth (node ): if node == None : return 0 a = depth(node.left) + 1 b = depth(node.right) + 1 return max (a,b) depth = depth(root) return depth
NC62 平衡二叉树 描述： 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树 （Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
注：我们约定空树是平衡二叉树。
题解来自评论区
平衡二叉树_牛客博客 (nowcoder.net)
自顶向下的方法 先求出每一个节点的深度，然后用先序遍历的方式，来判断是不是平衡二叉树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution : def IsBalanced_Solution (self, pRoot ): note = dict () def depth (node ): if node == None : return 0 if node in note: return note[node] a = depth(node.left) + 1 b = depth(node.right) + 1 note[node] = max (a,b) return note[node] def judge (node ): if not node: return True return abs (note.get(node.left,0 )-note.get(node.right,0 ))<=1 and judge(node.left) and judge(node.right) depth(pRoot) return judge(pRoot)
自底向上的方式 然后对原始dfs的代码加以改造，如果不满足平衡二叉树的定义，则返回-1 ，并且如果左子树不满足条件了 ，直接返回-1，右子树也是如此，相当于剪枝，加速结束递归。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution : def IsBalanced_Solution (self, pRoot ): def dfs (node ): if node == None : return 0 a = dfs(node.left) if a == -1 : return -1 b = dfs(node.right) if b == -1 : return -1 sub = abs (a-b) if sub > 1 : return -1 return max (a,b)+1 res = dfs(pRoot) return res != -1
简化如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def height2 (self,root:TreeNode ): if not root: return 0 leftHeight = self.height2(root.left) rightHeight = self.height2(root.right) if leftHeight == -1 or rightHeight == -1 or abs (leftHeight-rightHeight) > 1 : return -1 else : return max (leftHeight,rightHeight) + 1 def isBalanced (self, root: TreeNode ) -> bool : return self.height2(root)>=0
NC16 判断二叉树是否对称
leetcode-100,101
递归 需要两个节点一起比较，如果两个节点都为空说明为对称节点。
如果一个为空说明不对称；
然后去比较两个节点值；
接着递归比较pq的外层，和内层
1 2 3 4 5 6 7 8 9 10 11 class Solution : def check (self,p:TreeNode,q:TreeNode ): if not p and not q: return True elif not p or not q: return False return p.val == q.val and self.check(p.left,q.right) and self.check(p.right,q.left) def isSymmetric (self , root ): return self.check(root,root)
队列 初始节点入队两次，每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。**(兄弟节点都是诶着的，内层跟内层比，外层跟外层比)**
当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续n结点）时，该算法结束。
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 class Solution : def isSymmetric (self , root ): if root == None : return True queue = list () queue.append(root) queue.append(root) while queue: p = queue.pop(0 ) q = queue.pop(0 ) if not p and q: return False elif p and not q: return False elif not p and not q: continue if p.val != q.val: return False queue.append(p.left) queue.append(q.right) queue.append(p.right) queue.append(q.left) return True
NC9 二叉树中是否存在节点和为指定值的路径 描述 给定一个二叉树和一个值$sum$，判断是否有从根节点到叶子节点的节点值之和等于$sum$ 的路径，
返回true，因为存在一条路径 $5\to 4\to 11\to 2$的节点值之和为 22。
解法 在原有的dfs基础上，增加一个全局变量，sumss
在遍历过程中sumss遇到没有子节点的节点就加一，然后递归遍历左右节点，
最后在减去当前节点的值，这里是回溯的思想
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution : def hasPathSum (self , root , sums ): self.flag = False if root == None : return self.flag self.sumss = 0 def depth (node:TreeNode ): if node == None : return self.sumss += node.val if not node.left and not node.right: if self.sumss == sums: self.flag = True depth(node.left) depth(node.right) self.sumss -= node.val depth(root) return self.flag
解法二
来自评论区
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution : def hasPathSum (self , root , sums ): self.flag = False if root == None : return self.flag self.sumss = 0 def depth (node:TreeNode,target:int ): if node == None : return False target -= node.val if not node.left and not node.right: if target == 0 : return True return depth(node.left, target) or depth(node.right,target) return depth(root,sums)
NC11 将升序数组转换为平衡二叉搜索树 描述 给出一个升序排序的数组，将其转化为平衡二叉搜索树（BST）.
示例
1 2 输入值：[-1,0,1,2] 返回值：{1,0,2,-1}
题解
来自牛客评论区
二叉搜索树，它的中序遍历后的结果就是一个升序的序列；
平衡的，说明任何一个节点的左子树和右子树的高度相差不超过1。
题目所给是一个升序数组，故大体流程就是根据一个中序遍历的序列，还原出对应的二叉树。
因为是中序遍历的结果，所以元素的左边都是以该元素为根节点的左子树上的元素，****元素的右边都是以该元素为根节点的右子树上的元素。
又因为是平衡的，所以先找出序列的中点，以中点的值生成根节点 ，他的左边右边相差不差过一个元素，即它的左子树和右子树的元素个数相差不超过一个，每次都安一样的策略来找根节点，即左右子树的高度相差不会超过1。
以中点的左边序列为一个新的序列，按照一样的方法生成一个平衡二叉树，该树是第一步找的根节点的左子树 。
以中点的右边序列为一个新的序列，按照一样的方法生成一个平衡二叉树，该树是第一步找的根节点的右子树 。
也就是把问题的规模拆分成一个一个的小规模问题，解法都是一样的，只是问题的规模不一样，到规模足够小的时候我们可以很方便的找出答案，再一步一步往上推回去，即可得到真个大规模问题的答案。
解法一：递归 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution : def sortedArrayToBST (self , num ): def dfs (left,right ): if left > right: return None mid = (left+right+1 ) // 2 root = TreeNode(num[mid]) root.left = dfs(left, mid-1 ) root.right = dfs(mid+1 ,right) return root return dfs(0 ,len (num)-1 )
解法二：用栈模拟递归
还是递归舒服
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 class Node : def __init__ (self,node:TreeNode,left:int ,right:int ): self.node = node self.left = left self.right = right class Solution : def sortedArrayToBST (self , num ): if len (num) == 0 : return None left = 0 right = len (num) - 1 mid = left + (right - left + 1 )//2 root = TreeNode(num[mid]) stack = list () stack.append(Node(root,left,right)) curRoot = root while left<right or len (stack) >0 : while left < right: right = mid - 1 mid = left+(right-left+1 )//2 leftNode = TreeNode(num[mid]) curRoot.left = leftNode curRoot = curRoot.left stack.append(Node(leftNode,left,right)) node = stack.pop() left = node.left right = node.right mid = left + (right-left+1 )//2 left = mid + 1 if left<= right: mid = left + (right - left + 1 )//2 curRoot = node.node rightNode = TreeNode(num[mid]) curRoot.right = rightNode curRoot = rightNode stack.append(Node(rightNode, left, right)) return root
NC5 二叉树根节点到叶子节点的所有路径和 描述 给定一个仅包含数字$0-9$ 的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。
例如根节点到叶子节点的一条路径是$1\to 2\to 3$,那么这条路径就用$123$ 来代替。
找出根节点到叶子节点的所有路径表示的数字之和
例如：
这颗二叉树一共有两条路径，
解法：DFS 和前面的套路一样
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 sumNumbers (self , root ): ress = [] temp = [] def dfs (node:TreeNode ): if node == None : return temp.append(node.val) if not node.left and not node.right: fuckyou = '' .join(map (str ,temp.copy())) ress.append(fuckyou) dfs(node.left) dfs(node.right) temp.pop() dfs(root) ress = map (int ,ress) return sum (ress)
解法：BFS
来自评论区
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 sumNumbers (self , root:TreeNode ): if root == None : return 0 nodeQueue = list () valueQueue = list () res = 0 nodeQueue.append(root) valueQueue.append(root.val) while len (nodeQueue) > 0 : node = nodeQueue.pop() val = valueQueue.pop() if not node.left and not node.right: res += val else : if node.left != None : nodeQueue.append(node.left) valueQueue.append(val*10 + node.left.val) if node.right != None : nodeQueue.append(node.right) valueQueue.append(val*10 + node.right.val) return res
NC58 找到搜索二叉树中两个错误的节点 描述 一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)
解法：中序遍历+查找 中序遍历加找异常位置的元素,
因为此时的情况必定是一个小的数放到了后面，一个大的数放到了前面所以从左往右找那个大的数，并记录下索引，从右往左找小的那个数，并且索引值必大于前面记录下的索引
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 class Solution : def findError (self , root ): nums = [] def dfs (node:TreeNode ): if node == None : return dfs(node.left) nums.append(node.val) dfs(node.right) dfs(root) ans = [] for i in range (len (nums)-2 ,-1 ,-1 ): if nums[i] > nums[i+1 ]: ans.append(nums[i+1 ]) break for i in range (1 ,len (nums)): if nums[i]<nums[i-1 ]: ans.append(nums[i-1 ]) break return ans
解法：递归+判断
见牛客评论区
NC12 重建二叉树
leetcode-106 依据后序遍历和遍历，构建二叉树
给定某二叉树的前序遍历和中序遍历，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
解法：递归 来自评论区
二叉树的前序遍历：根左右 ；中序遍历：左根右 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution : def reConstructBinaryTree (self, pre, vin ): if not pre: return None root = TreeNode(pre[0 ]) tmp = vin.index(pre[0 ]) root.left = self.reConstructBinaryTree(pre[1 :tmp+1 ], vin[:tmp]) root.right = self.reConstructBinaryTree(pre[tmp+1 :], vin[tmp+1 :]) return root
解法：双指针 见牛客评论区
NC109 岛屿数量 描述 给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
示例1
1 2 3 [[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]] 3
解法：DFS 来自评论区
遍历整块大陆，横着竖着遍历都可以。
第一次碰到陆地的时候，就知道这是块岛屿了，所以将这块陆地放入探险队列，岛屿数量加一。
然后我们将这块岛屿的陆地探索完。 每一次将这块陆地周围（上下左右）的陆地放入队列，然后将这块陆地标记为已探索 （这里就直接置为’0’了）。
当探险队列为空时，表示这块岛屿的陆地全部被探索完了，我们继续寻找下一块陆地。
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 class Solution : def solve (self , grid ): if grid == None or len (grid) == 0 : return 0 self.nr = len (grid) self.nc = len (grid[0 ]) def dfs (r:int ,c:int ): if r<0 or c<0 or r >= self.nr or c>=self.nc or grid[r][c] == '0' : return grid[r][c] = '0' dfs(r - 1 ,c) dfs(r + 1 ,c) dfs(r, c - 1 ) dfs(r, c + 1 ) num_islands = 0 for r in range (self.nr): for c in range (self.nc): if grid[r][c] == '1' : num_islands += 1 dfs(r,c) return num_islands
解法：BFS 从一个为1的根节点开始访问，每次向下访问一个节点，直到访问到最后一个节点。
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 class Solution : def solve (self , grid ): if grid == None or len (grid) == 0 : return 0 self.nr = len (grid) self.nc = len (grid[0 ]) def bfs (i:int ,j:int ): queue = list () queue.append(i*self.nc + j) while len (queue) > 0 : id = queue.pop() r = id // self.nc c = id % self.nc if r-1 >= 0 and grid[r-1 ][c] == '1' : queue.append((r - 1 )* self.nc + c) grid[r-1 ][c] = '0' if r+1 < self.nr and grid[r+1 ][c] == '1' : queue.append((r+1 )* self.nc +c) grid[r+1 ][c] = '0' if c-1 >= 0 and grid[r][c-1 ] == '1' : queue.append(r * self.nc + c - 1 ) grid[r][c-1 ] = '0' if c+1 < self.nc and grid[r][c+1 ] == '1' : queue.append(r*self.nc + c + 1 ) grid[r][c+1 ] = '0' num_islands = 0 for r in range (self.nr): for c in range (self.nc): if grid[r][c] == '1' : num_islands += 1 bfs(r,c) return num_islands
NC60 判断一棵二叉树是否为搜索二叉树和完全二叉树
二叉搜索树，既二叉排序树
完全二叉树，设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，
描述 给定一棵二叉树，已知其中的节点没有重复值，请判断该二叉树是否为搜索二叉树和完全二叉树。
解法 使用dfs进行中序遍历，获取升序的数组，如果数组中出现不是升序的，则说明不是搜索二叉树。
使用bfs进行层序遍历，来查看是否有不连续的叶子节点。这里具体的操作是不判断叶子节点是否为空，直接加入。
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 class Solution : def judgeIt (self , root ): self.flag1 = True self.flag2 = False self.nodeCount = 0 self.depth = 0 nums = [] def dfs (node:TreeNode ): if node == None : return 0 self.nodeCount += 1 dfs(node.left) nums.append(node.val) dfs(node.right) def bfs (): queue = list () queue.append(root) flag = False while len (queue)>0 : p = queue.pop(0 ) if p == None : flag = True continue if flag: return False queue.append(p.left) queue.append(p.right) return True dfs(root) for i in range (1 ,len (nums)): if nums[i] < nums[i-1 ]: self.flag1 = False self.flag2 = bfs() return [self.flag1,self.flag2]
NC138 矩阵最长递增路径 描述 给定一个 n行 m 列矩阵 matrix ，矩阵内所有数均为非负整数。
求一条路径，该路径上所有数是递增的。
这个路径必须满足以下条件：
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外。
你不能走重复的单元格。即每个格子最多只能走一次。
解法 参考牛客评论区
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 class Solution : def solve (self , matrix ): self.rows = len (matrix) self.cols = len (matrix[0 ]) temps = [] paths = [ [0 for _ in range (self.cols)] for _ in range (self.rows) ] def dfs (i:int ,j:int ,pre:int ): if matrix[i][j] <= pre: return 0 if paths[i][j] > 0 : return paths[i][j] cur_max = 0 if i>0 : cur_max = max (dfs(i-1 ,j, matrix[i][j]), cur_max) if i < self.rows-1 : cur_max = max (dfs(i+1 , j, matrix[i][j]), cur_max) if j > 0 : cur_max = max (dfs(i, j-1 , matrix[i][j]), cur_max) if j < self.cols-1 : cur_max = max (dfs(i, j+1 , matrix[i][j]), cur_max) paths[i][j] = cur_max+1 return paths[i][j] max_ = 0 for i in range (self.rows): for j in range (self.cols): max_ = max (max_,dfs(i, j,-1 )) return max_
WC152 矩阵中的路径 描述 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
例如$\left[ \begin{array} { l l l l } a & b & c & e \ s & f & c & s \ a & d & e & e \end{array} \right]$，矩阵中包含一条字符串“bcced”的路径，但是矩阵中不包含“abcd”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
解法：回溯 来自评论区：【数据结构和算法】回溯算法解矩阵中的路径_牛客博客 (nowcoder.net)
采用回溯的思想。
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 class Solution : ''' 可以在四个方向上查找，所以是一个四叉树 ''' def dfs (self,matrix,word,i,j,index ): ''' index：用于记录字符串迭代的位置 ''' if i >= self.rows or i <0 : return False if j >= self.cols or j <0 : return False if matrix[i][j] != word[index]: return False if index == len (word)-1 : return True temp = matrix[i][j] matrix[i][j] = "." res = False res = self.dfs(matrix,word, i + 1 , j, index + 1 ) res |= self.dfs(matrix,word, i - 1 , j, index + 1 ) res |= self.dfs(matrix,word, i, j + 1 , index + 1 ) res |= self.dfs(matrix,word, i, j - 1 , index + 1 ) matrix[i][j]=temp return res def hasPath (self , matrix , word ): if len (word) == 0 : return False self.rows = len (matrix) self.cols = len (matrix[0 ]) for i in range (self.rows): for j in range (self.cols): if self.dfs(matrix,word,i,j,0 ): return True return False
NC613 新集合-较难 描述 集合$s$中有整数 $1$ 到$n$，牛牛想从中挑几个组成一个新的集合。
现在牛妹给牛牛加了 $m$ 个限制，每个限制包含两个整数 $u$ 和 $v$ ($u\neq v$)，且 $u$ 和 $v$ 不能同时出现在新集合中。
请问牛牛能组成的新集合多少种。
可以选0个数。
返回一个整数，既新集合的种类数。
解法：递归 来自评论区 题解 | #新集合#_牛客博客 (nowcoder.net)
根据限制数组，建立图的邻接矩阵
通过递归的方式枚举所有的集合
如果之前出现的数和当前数同时出现在图中，则不可行，直接返回。否则列出所有可行的集合，每列出一个集合，计数加一。
实现：
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 class Solution : def solve (self , n , m , limit ): graph = [[0 for _ in range (n+1 )] for _ in range (n+1 )] used = [False ] * (n+1 ) self.res = 0 for t in limit: x,y = t.x,t.y graph[x][y]=graph[y][x] = 1 print (graph) def dfs (idx ): if idx>n: self.res+=1 return dfs(idx+1 ) for j in range (idx): if used[j] and graph[idx][j] == 1 : return used[idx] = True dfs(idx+1 ) used[idx] = False dfs(1 ) return self.res
