【leetcode】543：Diameter of Binary Tree

Posted on

二叉树的直径

难度：Easy

题目描述

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

示例

给定二叉树 

1
2
3
4
5
1
     / \
    2   3
   / \     
  4   5

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

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

1
2
3
4
5
6
7
8
9
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        int res = getHeight(root->left) + getHeight(root->right);
        return max(res, max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)));
    }
    int getHeight(TreeNode* node) {
        if (!node) return 0;
        if (m.count(node)) return m[node];
        int h = 1 + max(getHeight(node->left), getHeight(node->right));
        return m[node] = h;
    }

private:
    unordered_map<TreeNode*, int> m;
};

思路：

其实就是根结点的左右两个子树的深度之和再加1。那么我们只要对每一个结点求出其左右子树深度之和，再加上1就可以更新结果了。为了减少重复计算，我们用哈希表建立每个结点和其深度之间的映射，这样某个结点的深度之前计算过了，就不用再次计算了。

知识点：