Leetcode543. 二叉树的直径

2021年4月27日 207点热度 1人点赞 0条评论

题目描述

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

示例 :
给定二叉树

          1
         / \
        2   3
       / \     
      4   5    

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

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

解题思路

这道题可以借鉴Leetcode124. 二叉树中的最大路径和中的思路,用相似的DFS搜索方法来求解。

这道题相比较最大路径和,要简单了很多。我们需要求解左子树和右子树的层数,并且用左子树与右子树的和去更新路径长度最大值maxPath的值,而返回左子树与右子树层数的最大值加上根节点(1)的值。

具体步骤如下:

  • 如果结点为空节点,返回为0;
  • leftright来标记左子树和右子树的层数。然后用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;
}

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论