• 前言

    这个题很好的考察了DFS的变形，以及对问题分析的能力。十分推荐。

    • 切记：把问题想清楚了再编写代码！

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

    示例 :

    给定二叉树

    1.       1
    3.      / \
    5.     2   3
    7.    / \     
    9.   4   5

    返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

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

    =======================================================================
    分析：两个结点之间的路径长度等于这条路径经过结点个数num-1,
    所以，求直径(最大路径值)等价于求路径经过点数总数-1;
    任意一条路径可以看成以某个结点为根节点，其左子树和右子树向下遍历路径拼接得到。

    解答：对于结点node, 其左子树向下遍历经过最多节点数为L, 也就是左子树为根节点的最大深度；
    其右子树向下遍历经过最多节点数为R, 也就是右子树为根节点的最大深度；
    那么，以node为起点经过的最大结点数为L + R + 1;

         记：以node_i为起点的路径经过结点最大数为d_node_i, 那么整个二叉树的直径就是max(d_node_i) - 1

     定义一个递归函数depth(TreeNode *node), 那么以该结点为根节点的最大深度为max(L, R) + 1<br />                        该结点的d_node = L + R + 1;<br />    <br />    递归搜索每个节点并设一个全局变量ans记录d_node的最大值，最后返回 ans-1 即为树的直径。<br />=======================================================================

    /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int depth(TreeNode * node, int & ans)
    {
        if (!node) return 0;
        int L = depth(node->left, ans);   // node左子树最大深度
        int R = depth(node->right, ans);  // node右子树最大深度
        ans = max(ans, L + R + 1);        // ans记录经过的最大节点数
        return max(L, R) + 1;             // 以node为根节点的最大深度
    }

    int diameterOfBinaryTree(TreeNode* root) 
    {
        int ans = 1;
        depth(root, ans);
        return ans - 1;   // 最大直径等于经过的最多节点数-1.
    }
};

    欢迎交流，批评指正！