思路： 1、深度优先遍历整个树dfs，每遍历一个节点，sum减去当前节点的val 2、如果到达叶子节点（左右子树均为空），sum为0，则说明该路径满足条件，返回True 3、如果遍历到最后，也每返回True，说明不存在满足条件节点，返回False # class TreeNode: class Solution: def hasPathSum(self , root: TreeNode, sum: int) -> bool: # dfs if not root: return False return self.dfs(root, sum) def dfs(self, root, sum...

思路： 1、末尾为根节点，左子树小于根节点，右子树大于根节点，找到左、右子树分界点，左子树中存在大于根节点的，则False 2、递归判断左、右子树数组是否同样满足 注意： 1、初始节点如果列表为空，则返回False 2、判断函数中，若递归判断到空列表，则返回True class Solution: def VerifySquenceOfBST(self , que: List[int]) -> bool: # write code here if len(que) == 0: return False return self.check(que) def check(self, que)...

思路： 两个函数，主函数，check函数 1、check，递归判断当前节点，左，右节点是否相同  子树结构先为空，则说明子树全部判断完，返回True 子树不为空，主树为空，则说明子树没判断完，主树无节点判断了，返回False  2、主函数，递归check树的当前节点，当前节点左，右子树的情况 class Solution: def HasSubtree(self , pRoot1: TreeNode, pRoot2: TreeNode) -> bool: if not pRoot1 or not pRoot2: return False return self.check(pRoot1,...

思路：层次遍历，基数层节点翻转 注意： 1、注意每次只处理当前层的节点，而不是遍历que中的全部节点 2、for循环之外为层级别的处理，for循环内部为层内节点级别的处理 3、每处理一个que中的节点，要将其pop，否则处理下一层节点时，还会重复处理 class Solution: def Print(self , p: TreeNode) -> List[List[int]]: # write code here if not p: return [] que = [p] level = 0 result = [] while que: l = len(que) cur_layer =...

思路： 1、快慢双指针，先判断是否有环，无环返回NULL，有环找到环内第一次交点 2、然后快指针回到链表头，与慢指针一起单步遍历 3、第二次相遇，既为入口地址 注意： **找环内第一个相遇点时，一定要先移动指针，再判断是否相遇，因为初始化快慢指针均指向链表头，如果不移动，则直接满足相遇并退出**  class Solution: def EntryNodeOfLoop(self, pHead): if not pHead: return slow, fast = pHead, pHead # 找环内第一次相遇点 while True: # 快慢指针先移动再判断，如果以fast及fast.nex...

思路: 与链表的第一个公共节点思路类似，使用公共set，第一个重复出现的节点既入口 class Solution: def EntryNodeOfLoop(self, pHead): if not pHead: return node_set = set() p1 = pHead while p1: if p1 not in node_set: node_set.add(p1) else: return p1 p1 = p1.next return

思路：双指针交叉遍历两个链表，再次重合既为第一个公共节点 class Solution: def FindFirstCommonNode(self , pHead1 , pHead2 ): if not pHead1 or not pHead2: return p1, p2 = pHead1, pHead2 while p1 != p2: p1 = p1.next p2 = p2.next if p1 == p2: break if not p1: p1 = pHead2 if not p2: p2 = pHead1 return p1

思路1：使用辅助集合，遍历过程中，如果遇到重复出现，既为第一个公共节点 注意： 1、指针为空，代表链表遍历结束 2、此方法也可以用来判断带环链表的入口位置 class Solution: def FindFirstCommonNode(self , pHead1 , pHead2 ): if not pHead1 or not pHead2: return node_set = set() p1, p2 = pHead1, pHead2 while p1: node_set.add(p1) p1 = p1.next while p2: if p2 in node_set: return p2 ...