leetcode-543

543. 二叉树的直径

1 题目描述

• 题目链接：543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例1：

输入: [1, 2, 3, 4, 5]
输出: 3
解释: 最长的路径为[4,2,1,3]或[5,2,1,3]

注意：两结点之间的路径长度是以它们之间边的数目表示。

2 思路

  直接深度优先遍历，DFS函数返回的是当前子树的最长路径长度，即最多边的路径。很显然，当找到叶节点时，此时该子树上只有一个节点，因而返回0。而最长的路径可能是当前根节点和左右子树中的节点所构成，即最长的路径经过根节点；或是最长的路径存在于左子树或右子树中。

  思考一下，最长路径经过了某个”根节点”(这里的根节点是当前遍历到的节点)，那么最长路径其实就是当前节点左右子树路径和，或左右子树路径长度中大者与其父节点相关的子树的路径长度和。因此，其实就是求当前节点(递归的当前层)的左右子树最长路径长度，而答案就是二者的和或是左右子树路径长度中较大者与上一层中的”子树”的路径加和。

int handle(struct TreeNode *root, int *cnt) {
    if(!root)   return -1;      // 空结点，返回-1，加完1后才是0条边
    else if (!root->left&&!root->right)   return 0; // 叶节点，无边

    int left = handle(root->left, cnt)+1;       // 左子树最长路径长度
    int right = handle(root->right, cnt)+1;     // 右子树最长路径长度
    *cnt = fmax(*cnt, left+right);              // 判断以过当前节点的路径是否为最长路径，是则更新答案
    return fmax(left, right);                   // 返回左右子树中的最长路径长度
}

int diameterOfBinaryTree(struct TreeNode* root){
    int ret = 0;
    handle(root, &ret);
    return ret;
}