思路:找二叉树中最长的路径,即找这么一个节点,它左右子树深度之和最大,求这个最大值。
class Solution {
public:
int deep(TreeNode* root, int& res)
{
if (root == nullptr) return 0; //空节点深度为0
int left = deep(root->left, res), right = deep(root->right, res);
res = max(res, left + right); //每次递归更新最大直径
return max(left, right) + 1; //返回当前节点最深的层数
}
int diameterOfBinaryTree(TreeNode* root) {
if (root == nullptr) return 0;
int res = 0;
deep(root, res);
return res;
}
};