Karl's Nest
0%

leetcode-day-11

Posted on In
Day-11 Diameter of Binary Tree

LeetCode 30 days Challenge - Day 11

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

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
    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.

Solution

题目要求分析：给定一棵二叉树，要求找到它的直径。二叉树直径定义为其中距离最远的两个节点之间的距离。

解法：

由题，我们知道直径不一定经过当前树的根结点。

因此，对以当前结点为根结点的（子）树，根据是否经过其根结点，可以分为两种情况，递归思想如下：

  1. 对于非空结点，计算：
    1. 左子树的深度 + 右子树的深度 = 经过当前结点的最长距离；
    2. 左子树的直径（递归，不经过根结点）；
    3. 右子树的直径（递归，不经过根结点）；
  2. 对以上三值，取最大值即为以当前结点为根的二叉树的直径。
1
2
3
4
5
6
7
8
9
int getdepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(getdepth(root->left), getdepth(root->right));
}
int diameterOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    int cur = getdepth(root->left) + getdepth(root->right);
    return max(cur, max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)));
}

传送门：Diameter of Binary Tree

Karl