题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是求二叉树中任意两个节点之间的最长路径（直径）。

思路分享

  • 两个任意节点的最长情况，无非就是叶子节点和另一个叶子节点，假设有一个不是叶子节点，那么将这个节点向下延申就会更长。那么两个叶子节点之间的距离怎么求呢？

  • 灵神的思路很好，通过转化成左右子树的深度就可以求出来了。

    https://leetcode.cn/problems/diameter-of-binary-tree/solutions/2227017/shi-pin-che-di-zhang-wo-zhi-jing-dpcong-taqma/

  • 下面的参考题解则是增加一个 cur 参数用于保存当前的深度，用左右子树深度各与当前深度差之和求答案。相比之下还是灵神的解法更妙。

代码解答（强烈建议自行解答后再看）

  • 参考题解
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
# 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:
        ans = 0
        def dfs(root: Optional[TreeNode]) -> int:
            if not root:
                return -1
            left = dfs(root.left) + 1
            right = dfs(root.right) + 1
            nonlocal ans 
            ans = max(ans, left + right)
            return max(left, right)
        dfs(root)
        return ans


        ans = 0
        def dfs(root: Optional[TreeNode], cur:int) -> int:
            if not root:
                return cur 
            cur = cur + 1
            left = dfs(root.left, cur)
            right = dfs(root.right, cur)
            # print(root.val, cur, left, right)
            nonlocal ans 
            ans = max(ans, left + right - 2 * cur)
            return max(left, right)
        dfs(root, 0)
        return ans