[LeetCode] 543. Diameter of Binary Tree

Given the root of a binary tree, return 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.

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

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 104].
-100 <= Node.val <= 100

二叉树的直径。

这道题同 LintCode 1181题。

题意是给一个二叉树，找二叉树里面的最大直径。最大直径的定义是任意两个 node 之间的最大距离。注意这个最大距离很有可能不经过根节点，如下图例子，最大直径是从 9 到 8，摘自LC中文网

油管上这个视频也讲的很好。

思路是后序遍历 postorder。做法类似104题找二叉树最大深度用到的递归，但是稍微做一点改动。设置一个全局变量记录 res 这个最大长度，递归函数找的依然是最大深度但是 res 记录的是经过当前节点的diameter。helper 函数往父节点 return 的则是一边的最长长度 + 1 = 一边的最长长度 + 当前这个子节点到父节点的距离。

照着这个例子跑一下吧，比如根节点的左孩子2这里。此时我需要知道的信息是经过2的 diameter 最长可以到多少，所以是 left + right。但是我往 2 的父节点 1 需要 return 的信息是经过2（同时也经过1）的最长的 diameter，我能贡献的长度是多少。这个长度是 2 的左右子树能贡献出来的较长者 + 1（2到1的距离）。

时间O(n)

空间O(n)

Java实现

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 class Solution {
11     int res = 0;
12 
13     public int diameterOfBinaryTree(TreeNode root) {
14         helper(root);
15         return res;
16     }
17 
18     private int helper(TreeNode root) {
19         // base case
20         if (root == null) {
21             return 0;
22         }
23         int left = helper(root.left);
24         int right = helper(root.right);
25         // 经过当前节点的直径是多长
26         res = Math.max(res, left + right);
27         // 但是往父节点return的时候，return的却是一边的最长长度 + 1 = 一边的最长长度 + 子节点到父节点的距离
28         return Math.max(left, right) + 1;
29     }
30 }

JavaScript实现

 1 /**
 2  * @param {TreeNode} root
 3  * @return {number}
 4  */
 5 var diameterOfBinaryTree = function (root) {
 6     let res = 0;
 7     var helper = function (root) {
 8         if (root == null) {
 9             return 0;
10         }
11         let left = helper(root.left);
12         let right = helper(root.right);
13         res = Math.max(res, left + right);
14         return Math.max(left, right) + 1;
15     };
16     helper(root);
17     return res;
18 };

[LeetCode] 543. Diameter of Binary Tree

推荐阅读