LC 543. Diameter of Binary Tree
题目描述
Leetcode 543 给定一个二叉树返回所有二叉树中两个点之间的最长路径，两个点可以是任意两个点
题目思路
可以采用分治法的方式，递归中返回到当前点时的最大距离，记录左右子树到当前节点的距离，然后在当前节点有两种处理方法：1.合并左右返回的最大距离与当前最长路径打擂台 2. 去左右返回的最大距离中最大的继续向上找可能更大的结果
代码如下
class Solution {
public:
int res = 0;
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return res;
}
int dfs(TreeNode* root) {
if (!root) return 0;
int l = dfs(root->left);
int r = dfs(root->right);
res = max(res, l+r);
return max(l+1, r+1);
}
};时间复杂度： N为所有节点个数
空间复杂度： H为递归深度