来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/diameter-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
一、题目描述
给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1 2 3 4 5 |
1 / \ 2 3 / \ 4 5 |
返回 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。
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 |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int diameterOfBinaryTree(TreeNode* root) { unsigned int diameter = 1; depth(root, diameter); return diameter - 1; } private: int depth(TreeNode *node, unsigned int &diameter) { unsigned int lDepth, rDepth; if (node == NULL) { return 0; } lDepth = depth(node->left, diameter); rDepth = depth(node->right, diameter); diameter = max(diameter, lDepth + rDepth + 1); return max(lDepth, rDepth) + 1; } }; |
复杂度分析:
- 时间复杂度:O(N),每个节点只访问一次。
- 空间复杂度:O(N),深度优先搜索的栈开销。
2020-03-10添加
为了完成leetcode每日1题打卡计划,使用golang重新提交了一次。
计算深度和直径的方式和上面略有不同,原理还是一样的:
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 |
func depth(root *TreeNode, diameter *int) int { if root == nil { return 0 } // 左子节点的深度 lDepth := depth(root.Left, diameter) + 1 // 右子节点的深度 rDepth := depth(root.Right, diameter) + 1 // 当前节点的直径 curDiameter := lDepth + rDepth - 1 // 更新最大的直径 if *diameter < curDiameter { *diameter = curDiameter } // 返回最大深度 if lDepth < rDepth { return rDepth } else { return lDepth } } func diameterOfBinaryTree(root *TreeNode) int { var diameter int diameter = 0 depth(root, &diameter) return diameter } |
评论