熊二 | C++ | #牛群的最长距离#

题目考察的知识点

• 二叉树
• 递归

题目解答方法的文字分析

一条路径的长度为该路径经过的节点数减一.则牛群的最长距离为该路径上的节点数减一。而一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。 深度优先遍历, 递归找到每个节点左右子树的最大深度之和，找出最大那一个即可。

遍历每个节点，统计每个节点能形成的最大直径

本题解析所用的编程语言

• cpp

完整且正确的编程代码

class Solution {
    // 计算二叉树的直径
    int ans = 0;

public:
    int diameterOfBinaryTree(TreeNode* root) {
        helper(root);
        return ans;
    }
    // 返回以该节点为根的树的最大深度
    int helper(TreeNode* node) {
        if (!node) return 0;
        int left = helper(node->left);
        int right = helper(node->right);
        if(left+right>0)ans = max(ans, left + right);
        return max(left, right)+1;
    }
};
/*
2023年8月8日，自己
*/

EOF