题目描述
给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意:两结点之间的路径长度是以它们之间边的数目表示。
解题思路
这道题可以借鉴Leetcode124. 二叉树中的最大路径和中的思路,用相似的DFS搜索方法来求解。
这道题相比较最大路径和,要简单了很多。我们需要求解左子树和右子树的层数,并且用左子树与右子树的和去更新路径长度最大值maxPath
的值,而返回左子树与右子树层数的最大值加上根节点(1)的值。
具体步骤如下:
- 如果结点为空节点,返回为0;
- 用
left
和right
来标记左子树和右子树的层数。然后用left+right
的值去更新路径长度最大值maxPath
的值; - 计算
max(left,right)+1
的值,将其作为返回值返回。max(left,right)+1
表示的意思就是当前结点可以返回的最大值,它的值为左子树与右子树层数的最大值加上根节点(1)。
时间复杂度:$O(N)$,其中 $N$为二叉树的节点数
空间复杂度:$O(Height)$,其中 $Height $为二叉树的高度
根据算法写出的示例代码如下。
示例代码
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
int dfs(TreeNode* root,int &maxPath)
{
if(!root) return 0;
int left=dfs(root->left,maxPath);
int right=dfs(root->right,maxPath);
if(left+right>maxPath)
{
maxPath=left+right;
}
return max(left,right)+1;
}
int diameterOfBinaryTree(TreeNode* root)
{
if(!root) return 0;
int maxPath=0;
dfs(root,maxPath);
return maxPath;
}
文章评论