【LeetCode】543. 二叉树的直径_leetcode 543. 二叉树的直径

1.题目

这道题和判断一棵二叉树是否是平衡二叉树非常相似。

2.思想

抽象定义问题的能力很重要！ 我们在写题的时候，逻辑一定要清楚，即脑子要先把整个过程过一遍，然后再来编码。

我们为每个节点获取如下两个值：

• （1）每个节点的高度值，（从其叶子节点到该节点的高度，左右子树取较大值）
• （2）每个节点的结果值（也就是每个节点所在树的直径）

最后即可发现，这个过程其实就是一个递归寻找最大直径的过程，完毕！

3.代码

'''
抽象定义问题的能力很重要！
思想
（1）获取每个节点的高度值，（从其叶子节点到该节点的高度，左右子树取较大值）
（2）获取每个节点的结果值（也就是每个节点所在树的直径）
'''

# 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:
    # 给定根节点root
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:        
        res,hight = self.dfs(root)
        return res

    # 判断当前节点为根节点时的最大值
    # hight 当前节点的树高
    # res 最后的结果
    def dfs(self,root):
        if root.left is None and root.right is None:
            return (0,0) # 当前节点的高度值为0，结果为0
        if root.left is not None:
            left_res,left_hight = self.dfs(root.left) # 左子树的情况            
            left_hight += 1 # 这里的加一非常重要，否则后面计算会始终少一个数
        else:
            left_res,left_hight = 0,0

        if root.right is not None:
            right_res,right_hight = self.dfs(root.right) # 右子树的情况            
            right_hight += 1
        else: # 如果右子树为空
            right_res,right_hight = 0,0

        # 比较二者的值情况    
        res = max(left_res,right_res,left_hight + right_hight)
            
        # 前者是最后的结果； 后者是当前节点的高度是左右子树高度的较大值，用做当前节点的高度
        return (res,max(left_hight,right_hight) ) # 返回两个值
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
36
37
38
39
40
41
42
43

今天重新写了一下代码，发现更加简洁了：

# 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 __init__(self):
        self.res = 0

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.get_height(root)
        return self.res-1

    def get_height(self,root,):
        if root is None: # 如果为空，直接返回0
            return 0
        left_num = self.get_height(root.left) # 返回左子树的高度
        right_num = self.get_height(root.right) # 返回右子树的高度

        self.res = max(self.res,left_num+right_num+1)
        return max(left_num,right_num) + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22