刷题之二叉树的直径（leetcode）

二叉树的直径

知道可以深度优先搜索，但是还是忍不住用左右子树的深度来计算。

土方法：算每个节点左右子树的深度，进而算出经过该节点的最大路径，进而算出整棵树的最大路径。

/**
 * 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 m=0;//记录最大路径
    int sort(TreeNode* root)
    {
        //确定终止条件
        //当递归到叶子节点时，叶子节点的左右节点最大深度为0
        if(root==NULL)
            return 0;
        //确定单层递归逻辑
        int left=sort(root->left);
        int right=sort(root->right);
        if(m<left+right)//记录经过每个节点的最大路径，可以是不经过头结点的路径
            m=left+right;
        return 1+max(left,right);
    }
    int diameterOfBinaryTree(TreeNode* root) {
        int result=0;
        int left=0;
        if(root==NULL)
            return 0;
        int num=sort(root->left)+sort(root->right);
        if(m<num)
            m=num;
        return m;
    }
};

代码随想录解法：

class Solution {
    int ans;
    int depth(TreeNode* rt){
        if (rt == NULL) {
            return 0; // 访问到空节点了，返回0
        }
        int L = depth(rt->left); // 左儿子为根的子树的深度
        int R = depth(rt->right); // 右儿子为根的子树的深度
        ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans
        return max(L, R) + 1; // 返回该节点为根的子树的深度
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/diameter-of-binary-tree/solutions/139683/er-cha-shu-de-zhi-jing-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

差别不大，咱就是说，自己的土方法怎么不算深度优先遍历呢hh