跳转至

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) 。