心之所向便是光

Leetcode 543.二叉树的直径

  • 2021-08-17
  • 作者 Ender
  • 1125 字
  • 次阅读

题目描述：

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

示例：

1
2
3
4
5
6
7
8
给定二叉树

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

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

链接：

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

题目分析

  这道题很像 Leetcode 124.二叉树中的最大路径和。那道题中路径的概念和这道题是一样的，那我们的做法也可以是一样的。我们利用 DFS 对二叉树进行遍历，而返回值和计算最大路径长度是分开的。返回值是该节点子树的深度，而以当前结点为根的最大路径长度则是左右子树返回值之和。
  我们使用一个类的成员变量来表示出现过的最大路径长度（也就是要求的直径）。在遍历中将计算每个点作为根的最大路径长度（左右子树的最大深度之和），然后返回自己的深度（也就是左右子树的最大深度加上 1），供给上层节点使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    int maxD = 0;
    
    int maxdepth(TreeNode* node){
        if(node == nullptr) return 0;
        int leftdepth = maxdepth(node->left);
        int rightdepth = maxdepth(node->right);
        maxD = max(maxD, leftdepth + rightdepth);
        return max(leftdepth, rightdepth) + 1;
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        maxdepth(root);
        return maxD;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。我们对二叉树进行了一次遍历。
  空间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。递归的最大深度为 $n$。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
, ,
最后编辑：2021-08-18