题目

PS:下列题目均来自leetcode中灵神题单

938. 二叉搜索树的范围和

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        if not root:
            return 0
        if root.val > high:
            return self.rangeSumBST(root.left, low, high)
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)
        return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)

2385. 感染二叉树需要的总时间

class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        G=defaultdict(list)
        def dfs(root):
            if root:
                if root.left:
                    G[root.val].append(root.left.val)
                    G[root.left.val].append(root.val)
                    dfs(root.left)
                if root.right:
                    G[root.val].append(root.right.val)
                    G[root.right.val].append(root.val)
                    dfs(root.right)
        dfs(root)

        q = deque([[start, 0]])
        vis=set()
        vis.add(start)
        while q:
            val,time=q.popleft()
            for around in G[val]:
                if around not in vis:
                    q.append([around, time + 1])
                    vis.add(around)
        return time

112. 路径总和

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def search(root,pathval):
            if not root:
                return False            
            pathval += root.val
            if not root.left and not root.right:
                return pathval == targetSum           
            return search(root.left,pathval) or search(root.right,pathval)      
        return search(root,0)

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def search(root,sum):
            if not root:
                return False
            sum-=root.val

            if not root.left and not root.right:
                if sum==0:
                    return True
                return False
            
            return search(root.left,sum) or search(root.right,sum)
        return search(root,targetSum)