543-二叉树的直径.md

思路：遍历每一个节点，以每一个节点为中心点计算最长路径（左子树边长+右子树边长），更新全局变量max。

/**
 * 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 max_depth = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == nullptr) return 0;
        dfs(root);
        return max_depth ;
    }
    int dfs(TreeNode* root) {
        if (root->left == nullptr && root->right == nullptr) return 0;//注意是左右子树都走到底了或者根本没有左右子树就返回
        int left_dia = (root->left) ? dfs(root->left) + 1 : 0;
        int right_dia = (root->right) ? dfs(root->right) + 1 : 0;
        max_depth = max(max_depth, left_dia+right_dia);
        return max(left_dia, right_dia);
    }
};