( “树” 之 DFS) 543. 二叉树的直径 ——【Leetcode每日一题】

543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :

给定二叉树

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意 ：两结点之间的路径长度是以它们之间边的数目表示。

思路：DFS

注意: 任意两个节点之间的边数都可能是最大直径, 最大的直径不一定包括根节点!

最大值不一定包含根节点，但是一定经过某一个节点;

经过该节点 左右子树的最大高度之和 即为最大直径; 于是，可以使用 DFS，求每个节点左右子树的最大高度之和，取出最大值 maxdia,即为结果:

• 定义一个全局变量 maxdia，用来记录最大直径, 使用 height(root) 遍历所有的节点，height(root) 的作用是：找出以 root 为根节点的左右子树的最大高度;
• maxdia 取值为以经过 root为根节点的左右子树的最大高度之和 ,为left + right;
• 以root 为左子树或右子树的高度为 Math.max(left, right) + 1, 返回给root的父节点,;
• 通过递归，找到 maxdia 的最大值.

代码：(Java、C++)

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 {private int maxdir = 0;public int diameterOfBinaryTree(TreeNode root) {if(root == null) return 0;height(root);return maxdir;}public int height(TreeNode root){if(root == null) return 0;int left = height(root.left);int right = height(root.right);maxdir = Math.max(maxdir, left + right);return 1 + Math.max(left, right);}
}

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:int maxdia = 0;int diameterOfBinaryTree(TreeNode* root) {if(root == NULL) return 0;height(root);return maxdia;}int height(TreeNode* root){if(root == NULL) return 0;int left = height(root->left);int right = height(root->right);maxdia = max(maxdia, left + right);return 1 + max(left, right);}
};

运行结果：

复杂度分析：

• 时间复杂度：$O(n)$，其中 n 为二叉树的节点数，即遍历一棵二叉树的时间复杂度，每个结点只被访问一次。
• 空间复杂度：$O(Height)$，其中 Height 为二叉树的高度。由于递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，而递归的深度显然为二叉树的高度，并且每次递归调用的函数里又只用了常数个变量，所以所需空间复杂度为 $O(Height)$。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我 leetCode专栏，每日更新！

注： 如有不足，欢迎指正！