543 二叉树的直径
/**
* Definition for a binary tree node.
* 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) {}
* };
*/
class Solution {
private:
// ans记录经过的节点数
// 两节点之间路径的长度由节点之间的边数表示
// 也就是说直径为ans - 1(节点数 - 1 = 边数)
int ans;
int depth(TreeNode* root){
// 注意边界条件
if(!root)
return 0;
// 计算根节点左右子树的最大深度(最大节点数)
int leftDepth = depth(root->left);
int rightDepth = depth(root->right);
// 更新本子树的最大节点数leftDepth + rightDepth + 1(1是根节点)
ans = max(ans, leftDepth + rightDepth + 1);
// 返回本子树的深度max(leftDepth, rightDepth) + 1(1是根节点)
return max(leftDepth, rightDepth) + 1;
}
public:
int diameterOfBinaryTree(TreeNode* root) {
if(!root)
return 0;
// 这个d其实并不重要,因为不一定经过root
int d = depth(root);
// 直径为最大节点数 - 1
return ans - 1;
}
};
复杂度分析
时间复杂度:O(N),其中 N 为二叉树的节点数,即遍历一棵二叉树的时间复杂度,每个结点只被访问一次。
空间复杂度:O(Height),其中 Height 为二叉树的高度。由于递归函数在递归过程中需要为每一层递归函数分配栈空间,所以这里需要额外的空间且该空间取决于递归的深度,而递归的深度显然为二叉树的高度,并且每次递归调用的函数里又只用了常数个变量,所以所需空间复杂度为 O(Height) 。