leetcode：543. 二叉树的直径

题目

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
注意：两结点之间的路径长度是以它们之间边的数目表示。

示例 1：
给定二叉树

  1.           1
  2.          / \
  3.         2   3
  4.        / \     
  5.       4   5

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

示例 2：
给定二叉树

  1.             7
  2.            /
  3.           1
  4.          / \
  5.         2   3
  6.        / \     
  7.       4   5

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

解答 & 代码

对于节点 cur，经过节点 **cur** 的二叉树直径的最大长度 = 左子树深度 + 右子树深度。
因此，需要先递归返回左右子树的深度，然后在后序位置得到经过节点 cur 的二叉树直径的最大长度，更新二叉树的直径最大值，并返回以节点 cur 作为根节点的树的深度。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. private:
  14.     int max_diam = 0;    // 二叉树直径的最大值
  15.     int dfs_height(TreeNode* root)
  16.     {
  17.         // 递归结束条件
  18.         if(root == nullptr)
  19.             return 0;
  21.         // 先递归得到左、右子树的深度
  22.         int left_max_height = dfs_height(root->left);
  23.         int right_max_height = dfs_height(root->right);
  24.         // 后序位置，计算经过当前节点的直径的最大长度
  25.         int cur_diam = left_max_height + right_max_height;
  26.         max_diam = max(max_diam, cur_diam);
  27.         // 返回以当前节点为根的树的深度
  28.         return 1 + max(left_max_height, right_max_height);
  29.     }
  30. public:
  31.     int diameterOfBinaryTree(TreeNode* root) {
  32.         dfs_height(root);
  33.         return max_diam;
  34.     }
  35. };

复杂度分析：设二叉树共 N 个节点

  • 时间复杂度 O(N)：遍历每个节点一次
  • 空间复杂度 O(log N)：栈空间取决于递归深度，即二叉树的高度

执行结果：

  1. 执行结果：通过
  3. 执行用时：8 ms, 在所有 C++ 提交中击败了 77.82% 的用户
  4. 内存消耗：19.7 MB, 在所有 C++ 提交中击败了 77.92% 的用户