LeetCode Hot100 | Day1 | 二叉树：二叉树的直径

LeetCode Hot100 | Day1 | 二叉树：二叉树的直径

紧张学习内容：
二叉树深度求法
深度的 left+right+1 得到的是从根结点到叶子结点的节点数目
543.二叉树的直径

[543. 二叉树的直径 - 力扣（LeetCode）](https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/)
解法思绪：

说之前先来看一种经典的错误。。

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

复制代码

哈哈想的是，左右子树最大深度求出来一加，直接完事了，惋惜的是这种是错误的

这个是错误示例，很显着，最长的直径在右子树上，而不是左子树加右子树的深度。
不外这也开导我们，分析思绪是对的，只是应该有一个记录最大值的变量，然后对每一个节点都举行一遍这个操纵，把最大的记录下来就是了
那接下来就是二叉树求深度
1.函数参数和返回值

1. int maxDepth=-1;
2. int tra(TreeNode *t)

复制代码

maxDepth记录最大直径，就是答案
返回值返回以当前结点为根结点的子树的深度
2.克制条件
直到没有数即没有结点要构建就是竣事

1. if(t==nullptr)
2.         return 0;

复制代码

碰到空了不加深度，直接返回0就行
3.本层代码逻辑

1. int left=tra(t->left);
2. int right=tra(t->right);
3. maxDepth=max(maxDepth,left+right+1);
4. return 1+max(left,right);

复制代码

left记录左子树深度
right记录右子树深度
更新以当前结点为子树的深度（l+r+1）和maxDepth之间的巨细，最大值赋值给maxDepth
更新后，返回上层递归函数当前子树的最大深度
完备代码：

1. class Solution {
2. public:
3.     int maxDepth=-1;
4.     int tra(TreeNode *t)
5.     {
6.         if(t==nullptr)
7.             return 0;
8.         int left=tra(t->left);
9.         int right=tra(t->right);
10.         maxDepth=max(maxDepth,left+right+1);
11.         return 1+max(left,right);
12.     }
13.     int diameterOfBinaryTree(TreeNode* root) {
14.         if(root==nullptr)
15.             return 0;
16.         int t=tra(root);
17.         return maxDepth-1;
18.     }
19. };

复制代码

末了注意：我们求的直径是边数，（l+r+1求的是节点数），要减去1才是边数。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金