543. Diameter of Binary Tree

发表于 | 分类于 | |

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree 

1
2
3
4
5
6
7
>           1
>          / \
>         2   3
>        / \     
>       4   5    
>
>

>

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

题意：叶子节点的最长距离（可不经过根节点）。

​ 做完二叉树的总结竟然经过自己独立并且一遍AC了！太开心了！果然老外的教程还是比较靠谱的，都怪自己的英语水平还达不到流畅地阅读，继续加油~

​ 做的思路是这样子的，以root为根节点，计算root左子树根节点(root->left)到叶子节点的最长距离(由countPath辅助完成)，再加上root右子树根节点(root->right)到右子树叶子节点的最长距离，这两个距离相加后再加上1(root本身)之后就是以root为根节点的叶子节点间的最长距离。

​ 然后遍历整棵树的所有节点，用ans为来维护最大值。遍历完后ans就是答案了。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//
// Created by chaopengz on 2017/11/7.
//

#include "head.h"


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int diameterOfBinaryTree(TreeNode *root)
    {
        if (!root)
            return 0;

        ans = max(countPath(root->left)+countPath(root->right)+1,ans);

        diameterOfBinaryTree(root->left);
        diameterOfBinaryTree(root->right);

        return ans-1;
    }

    int countPath(TreeNode *root)//count root to leaft
    {
        if (!root)
            return 0;
        else
            return max(countPath(root->left), countPath(root->right)) + 1;

    }

    int ans = 0;
};