543-二叉树的直径

2018年12月5日 评论

来源:力扣(LeetCode)

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

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一、题目描述

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

示例 :

给定二叉树

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

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

二、题解

本题最重要的一个点是要理清题意,求的是最大直径,是树内任意两点间的距离的最大值,不是求根节点到任意节点间距离的最大值(即深度)。

想法:

任意一条路径可以被写成两个箭头(不同方向),每个箭头代表一条从某些点向下遍历到孩子节点的路径。

假设我们知道对于每个节点最长箭头距离分别为L,R,那么最优路径经过L + R + 1个节点。

算法:

按照常用方法计算一个节点的深度:max(depth of node.left, depth of node.right) + 1。在计算的同时,经过这个节点的路径长度为1 + (depth of node.left) + (depth of node.right)。搜索每个节点并记录这些路径经过的点数最大值,期望长度是结果-1

复杂度分析:

  • 时间复杂度:O(N),每个节点只访问一次。
  • 空间复杂度:O(N),深度优先搜索的栈开销。

2020-03-10添加

为了完成leetcode每日1题打卡计划,使用golang重新提交了一次。

计算深度和直径的方式和上面略有不同,原理还是一样的:

543-二叉树的直径

匿名

发表评论

匿名网友