深度优先搜索与动态规划|543, 124, 687-Toy模板网

这篇具有很好参考价值的文章主要介绍了深度优先搜索与动态规划|543, 124, 687。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

二叉树的直径

好久没写二叉树了，主要还是看遍历的顺序是什么样的。

# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            nonlocal res
            if not root:
                return 0
            
            left = dfs(root.left)
            right = dfs(root.right)
            res = max(left + right,res)
            
            return max(left,right) + 1
        res = 0
        dfs(root)
        return res

二叉树中的最大路径和

深度优先搜索与动态规划|543, 124, 687,专题,深度优先,动态规划,算法,leetcode,数据结构,python

这个有点绕不出来。绕一遍，
root -10 进去，root.left是root 9，root.right是root 20
root 9 进去得到的return是9，res更新得到9
root 20进去，root.left是root 15，root.right是root 7
root 15进去得到的return是15，res更新得到15
root 7进去得到的return是7，res不跟新还是15
然后返回root 20，res会更新为20+15+9是42，但是这里的return是35（因为只能选一条路，走左边了就不能走右边，而这里左边比较大所以选左边）。
人后回root -10，res不更新，最后得到的答案就是42。

这里的return比较难想因为会忘记是一条路，不会回来的。

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            nonlocal res
            if not root:
                return 0
            
            left = max(dfs(root.left),0)
            right = max(dfs(root.right),0)
            max_dis = left+right+root.val
            res = max(res,max_dis)
            return root.val + max(left,right)
        res = -inf
        dfs(root)
        return res

最长同值路径

还是看错了！！是最长的路径，不是有几个一样的node连着，所以岔路了还要继续往上就可以选一条走了！！文章来源地址https://www.toymoban.com/news/detail-636335.html

class Solution:
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            nonlocal res
            if not root:
                return 0
            if not root.left and not root.right:
                return 0
            
            left = dfs(root.left)
            right = dfs(root.right)
            if root.left and root.val == root.left.val:
                left += 1
            else:
                left = 0
            
            if root.right and root.val == root.right.val:
                right += 1
            else:
                right = 0

            res = max(left+right,res)
            return max(left,right)
            

        res = 0
        dfs(root)
        return res