E-543. Diameter of Binary Tree

Loading...LeetCode

拿到题目, 第一个想法是找出所有点到点的长度, 然后挑出最大的那一个.

但是这只是个二叉树, 只有parent到child的指针, 没有child到parent也没有sibling之间的指针(如果有的话, 问题实际上更复杂了..)

那么我们要转换问题.

接着我们发现, 假如存在这么一条从node A到node B的最长路径, 那么这个路径上实际上存在那么一个peak node, 使得最长路径的长度等于这个peak node左子树中离他最远node A(或者B)到他的距离加上右子树中离他最远的node B(或者A)到他的距离.

而我们并不用关心node A和node B是谁, 也不用关心这个路径上的具体节点有哪些, 我们只需要输出最长路径长度即可. 所以, 问题可以转换为:

• 遍历树, 计算每一个节点到其左子树最深处(即左子树上距离它最远的那个node)和右子树最深的距离, 并求和deep_depth_n, 在n个节点中, 选出最大的那个deep_depth, 即为我们要找的结果.

又因为我们要遍历所有节点一次, 所以拿一个变量保留每次得到的deep_depth, 然后不断用新的比他大的deep_depth替换他.

# 1 
class Solution:
    def __init__(self):
        self.d_depth=0
        
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        def depth(root):
            if not root:
                return 0
            depth_left = depth(root.left)
            depth_right = depth(root.right)
            # 得到当前传进来的root的deep_depth是depth_right + depth_left
            # 然后拿这个deep_depth和全局的当前最大deep_depth比较, 保留更大的
            self.d_depth = max(self.d_depth, depth_right+depth_left)
            # 传给depth给上一个节点, 注意是要在左右里面选一个更大的, 并加1
            # 因为当前root和上一层节点中间还有个edge
            return max(depth_right,depth_left)+1
        depth(root)
        return self.d_depth

# 2 另一种写法, 可以更清晰地看到base case
class Solution:
    def __init__(self):
        self.d_depth=0
        
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        def depth(root, cur_depth):
            if not root:
                return 0
            depth_left = depth(root.left, cur_depth)
            depth_right = depth(root.right, cur_depth)
            self.d_depth = max(self.d_depth, depth_right+depth_left)
            cur_depth = max(depth_right,depth_left)+1 #<- base case
            return cur_depth
        depth(root, 0)
        return self.d_depth