LeetCode 热题 100_二叉树的直径（40_543_简单_C++）(二叉树；递归)

题目描述：

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

输入输出样例：

示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：
输入：root = [1,2]
输出：1

提示：
树中节点数目在范围 [1, 10⁴] 内
-100 <= Node.val <= 100

题解：

解题思路：

思路一（递归）：

1、我们可以采用和计算二叉树深度同样的思想，计算二叉树的深度是挑选左右子树中深度的最大值，而二叉树的直径是左子树的最大深度深度+右子树的最大深度。
2、复杂度分析：
① 时间复杂度：O(N)，其中 N 为二叉树的节点数，即遍历一棵二叉树的时间复杂度，每个结点只被访问一次。
② 空间复杂度：O(h)，其中 h 为二叉树的高度（递归需要额外的栈空间）。
本题的力扣官方题解链接（非常不错）

代码实现

代码实现（思路一（递归））：

//二叉树的直径
int diameterOfBinaryTree(TreeNode* root) {
    depth(root);
    return ans;
}

int depth(TreeNode *root){
    if(root==nullptr) return 0;
    
    //left：左子树的高度（高度指从叶结点开始测量）
    int left=depth(root->left);
    //right：右子树的高度
    int right=depth(root->right);
    
    //更新树的最大直径
    ans=max((left+right),ans);
 	// 返回当前节点的深度
    return max(left,right)+1;
}

以思路一为例进行调试

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

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 Soluton
{
    int ans=0;
    //注意递归返回的是深度，所以我们要分成两个函数
    int depth(TreeNode *root){
        if(root==nullptr) return 0;
        //left：左孩子子树的高度（高度指从叶结点开始测量）
        int left=depth(root->left);
        //right：右孩子子树的高度
        int right=depth(root->right);
        //求当前两节点间的最大长度
        ans=max((left+right),ans);
        return max(left,right)+1;
    }

public:
    //二叉树的直径
    int diameterOfBinaryTree(TreeNode* root) {
        depth(root);
        return ans;
    }

    //通过数组创建二叉树（数组元素为-1代表nullptr）
    TreeNode *creatTree(vector<int> nums){
        if(nums.empty()) return nullptr;
        TreeNode *root=new TreeNode(nums[0]);
        queue<TreeNode *> q;
        q.push(root);
        int i=1;
        while (i<nums.size())
        {
            TreeNode *node=q.front();
            q.pop();
            if(i<nums.size()&&nums[i]!=-1){
                node->left=new TreeNode(nums[i]);
                q.push(node->left);
            }
            ++i;
            if(i<nums.size()&&nums[i]!=-1){
                node->right=new TreeNode(nums[i]);
                q.push(node->right);
            }
            ++i;
        }
        
        return root;
    }

    //中序遍历输出二叉树(用于调试二叉树创建是否正确)
    void inorder(TreeNode *root){
        if(root==nullptr) return ;
        inorder(root->left);
        cout<<root->val<<" ";
        inorder(root->right);
    } 
};

int main(){
    vector<int> nums={1,2,3,4,5};
    Soluton s;
    //创建二叉树
    TreeNode *root=s.creatTree(nums);
    //调试二叉树是否创建正确
    //s.inorder(root); 
    cout<<"二叉树的直径:"<<s.diameterOfBinaryTree(root);
    return 0;
}

LeetCode 热题 100_二叉树的直径（40_543)原题链接
欢迎大家和我沟通交流(✿◠‿◠)