目录
题目链接：543. 二叉树的直径 - 力扣（LeetCode）
题目描述
示例
提示：
解法一：深度优先搜索
实现思路：
关键点：
Java写法：
运行时间
C++写法：
运行时间
总结
题目链接：543. 二叉树的直径 - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
题目描述
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例
示例 1：
输入：root = [1,2,3,4,5] 输出：3 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2] 输出：1
提示：
- 树中节点数目在范围
[1,内]
-100 <= Node.val <= 100
解法一：深度优先搜索
直径是二叉树中任意两节点间最长路径的长度。思路是通过深度优先遍历来逐个节点进行递归计算，最终找出最长路径。
实现思路：
-
全局变量
res的作用：- 该变量用于动态保存当前发现的最长路径。初始值设为
0，但在进入根节点时被初始化为1，因为树至少包含根节点。
- 该变量用于动态保存当前发现的最长路径。初始值设为
-
diameterOfBinaryTree方法：- 入口方法，接收二叉树的根节点作为输入。
- 首先检查根节点是否为空，若为空，则二叉树的直径为
0。 - 调用辅助方法
depthFirst，以深度优先的方式遍历整棵树。 - 最终返回
res - 1，这是因为路径的长度是节点数减1。
-
深度优先遍历
depthFirst：- 每个节点通过递归方式遍历其左子树和右子树，分别获取左子树和右子树的深度。
- 更新全局变量
res，这个过程通过比较当前节点左子树和右子树的深度和当前保存的res，取最大的那个值。res的更新逻辑是左子树深度 + 右子树深度 + 1（代表当前节点）。 - 返回当前节点的深度，即左子树和右子树深度的最大值加1，作为给上层节点使用的深度值。
关键点：
- 深度优先搜索 (DFS)：通过递归的方式遍历每一个节点。
- 动态维护最长路径：每次计算出左右子树的深度时，更新全局变量
res，并确保保存的是最长路径。 - 最终结果调整：二叉树的直径是节点数减去1（路径的长度是节点数减1），因此最后返回
res - 1。
Java写法：
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {// 定义一个全局变量用于动态保存resint res = 0;public int diameterOfBinaryTree(TreeNode root) {if(root != null){res = 1;}else{return 0;}// 深度优先遍历depthFirst(root);// 由于我们最终得到是节点的个数// 而题目要的是路径的长度，那么只需要-1即可return res - 1;}/**深度优先遍历*/public int depthFirst(TreeNode node){// 非空判断if(node == null){return 0;}// 遍历左子树int leftDepth = depthFirst(node.left);// 遍历右子树int rightDepth = depthFirst(node.right);// 动态维护res，由于我们要找的是最长两个节点的长度// 那么res的值=左子树的深度+右子树的深度+node节点(也就是1)res = Math.max(res, leftDepth + rightDepth + 1);// 返回当前树的深度给上一节点return Math.max(leftDepth,rightDepth) + 1;}
}运行时间
C++写法：
/*** 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 {
public:// 定义一个全局变量用于动态保存resint res = 0;int diameterOfBinaryTree(TreeNode* root) {if(root == NULL){return 0;}else{res = 1;}// 深度优先遍历depthFirst(root);// 由于我们最终得到是节点的个数// 而题目要的是路径的长度，那么只需要-1即可return res - 1;}/**深度优先遍历*/int depthFirst(TreeNode* node){// 非空判断，结束条件if(node == NULL){return 0;}// 遍历左子树int leftDepth = depthFirst(node->left);// 遍历右子树int rightDepth = depthFirst(node->right);// 动态维护res，由于我们要找的是最长两个节点的长度// 那么res的值=左子树的深度+右子树的深度+node节点(也就是1)res = max(res, leftDepth + rightDepth + 1);// 返回当前树的深度给上一节点return max(leftDepth,rightDepth) + 1;}
};运行时间
总结
其实就是深度优先搜索的一个扩展现实，多维护了一个res结果，在每次的深度优先搜索的过程中动态的维护一个res，来坚持判断当前两个最远的节点的值，这里最远的节点的值，肯定是存在于两个叶子结点之间的（其实我也在思考这句话对不对，我目前分析来说是对的，没有找到反例，不知道各位同学、大佬能不能发现这句话的问题，欢迎指正），这就是这道题目的关键点所在。
