543. 二叉树的直径¶

https://leetcode-cn.com/problems/diameter-of-binary-tree/

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 :

给定二叉树

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

最长路径有两种情况，过 root 节点和不过 root 节点：

二叉树的最长路径=max{左子树的最长路径,右子树的最长路径,经过根结点的最长路径}

经过根结点的最长路径 = 左子树的深度加上右子树的深度，所以：

二叉树的最长路径=max{左子树的最长路径,右子树的最长路径,左子树的深度+右子树的深度}

备注

时间复杂度：O(N)
空间复杂度：O(Height)，其中 Height 为二叉树的高度

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(node):
            if not node:
                return 0, 0
            left_depth, left_dia = dfs(node.left)
            right_depth, right_dia = dfs(node.right)

            # 最大深度
            depth = 1 + max(left_depth, right_depth)
            # 最长路径
            diameter = max(left_dia, right_dia, left_depth+right_depth)
            return depth, diameter
        depth, diameter = dfs(root)
        return diameter

上述方法中我们是根据 left_dia，right_dia 子树的最长路径来计算当前树的最长路径，那么可以用一个全局变量来保存

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            # 最长路径 = max{子树的最长路径, 左子树的深度+右子树的深度}
            self.diameter = max(self.diameter, left + right)
            # 返回最大深度
            return 1 + max(left, right)
        self.diameter = 0
        dfs(root)
        return self.diameter

543. 二叉树的直径¶

leetcode

导航

Related Topics