leetcode.cn/problems/smallest-subtree-with-all-the-deepest-nodes/">具有所有最深节点的最小子树

一开始题没看懂，他这里就是找到最深的叶子结点，看他们附近有没有公共祖先，如果有的话就意味着，这两个最深的叶子结点的深度是一样的，直接出他们附近的root，如果没有的话那其实就是看是不是他自己了。

python">class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def depth(root):
            if not root:
                return 0
            left = depth(root.left)
            right = depth(root.right)
            return max(left,right) + 1
        
        if not root:
            return None 
        left = depth(root.left)
        right = depth(root.right)
        if left == right:
            return root 
        elif left > right:
            return self.lcaDeepestLeaves(root.left)
        else:
            return self.lcaDeepestLeaves(root.right)

leetcode.cn/problems/longest-zigzag-path-in-a-binary-tree/">二叉树中的最长交错路径

这道题真的很难，就是不知道怎么控制方向，所以我们用了两个数字做result，一个代表接着往左走还有几个，另一个代表接着往右走还有几个，这里，如果第一步选择了root.left，那接着应该往右就是r1+1，如果第一步选择了root.right，那接着应该往左就是l2+1，往上想一步，root.left的上一层应该是属于再往上那颗的右节点，所以我们dfs(root.left)的想要的答案应该是那个右节点继续往左走的答案也就是l2+1，所以我们的return第二位的就是l2+1，反过来是一样的。

python">class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        res = 0
        def dfs(root):
            nonlocal res
            if not root:
                return -1, -1
            l1, r1 = dfs(root.left)
            l2, r2 = dfs(root.right)
            res = max(res,1+r1,l2+1)
            return 1+r1, l2+1
        dfs(root)
        return res

leetcode.cn/problems/path-with-minimum-effort/">最小体力消耗路径

例子都对了但提交的时候超时了。

python">class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        row = len(heights)
        col = len(heights[0])
        res = []
        result = []
        used = [[False]*col for _ in range(row)]
        used[0][0] = True
        def dfs(i,j):
            nonlocal res
            if i == row-1 and j == col-1:
                result.append(max(res))
                return 
            for k1,k2 in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
                if 0 <= k1 < row and 0 <= k2 < col and not used[k1][k2]:
                    if result and min(result) < abs(heights[i][j]-heights[k1][k2]): continue
                #if res and max(res) < abs(heights[i][j]-heights[k1][k2]): continue
                    res.append(abs(heights[i][j]-heights[k1][k2]))
                    used[k1][k2] = True
                    dfs(k1,k2)
                    used[k1][k2] = False
                    res.pop()
        
        if row == col == 1:
            return 0
        dfs(0,0)
        return min(result)

一个并查集的例子做到了再回来看。

python">class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m = len(heights)
        n = len(heights[0])
        fa = [i for i in range(m*n)]
        def find(x):
            if x == fa[x]:
                return x
            else:
                fa[x] = find(fa[x])
                return fa[x]
        edges = []
        for i in range(m):
            for j in range(n):
                to = i * n + j
                if i > 0:
                    edges.append((to - n,to,abs(heights[i][j] - heights[i - 1][j])))
                if j > 0:
                    edges.append((to - 1,to,abs(heights[i][j] - heights[i][j - 1])))

        edges.sort(key=lambda x:x[2])
        ans = 0
        for x,y,v in edges:
            fx,fy = find(x),find(y)
            fa[fy] = fx
            fs = find(0)
            fe = find(m*n - 1)
            if fs == fe:
                ans = v
                break
        return ans