LeetCode 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

 

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.

---

又是一道不会做的easy，菜菜。

思路大概和max depth差不多，一边求max depth，一边计算以当前这个root为root的max diameter，然后和全局的max做比较。复杂度都是O(n)。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Diameter of Binary Tree.

Memory Usage: 38.8 MB, less than 14.95% of Java online submissions for Diameter of Binary Tree.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { int numOfNodes = 0; public int diameterOfBinaryTree(TreeNode root) { if (root == null) { return 0; } depth(root); return numOfNodes - 1; } private int depth(TreeNode root) { if (root == null) { return 0; } int left = depth(root.left); int right = depth(root.right); numOfNodes = Math.max(numOfNodes, left + right + 1); return Math.max(left, right) + 1; } }

另外一种做法和我的想法挺像的，就是root的max dia是左子树的depth+右子树的depth，然后递归求左右子节点的max dia，和root做比较。但是因为有重复计算所以效率挺低的。

Runtime: 9 ms, faster than 13.15% of Java online submissions for Diameter of Binary Tree.

Memory Usage: 38.7 MB, less than 14.95% of Java online submissions for Diameter of Binary Tree.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int diameterOfBinaryTree(TreeNode root) { if (root == null) { return 0; } int rootDiameter = depth(root.left) + depth(root.right); int left = diameterOfBinaryTree(root.left); int right = diameterOfBinaryTree(root.right); return Math.max(rootDiameter, Math.max(left, right)); } private int depth(TreeNode root) { if (root == null) { return 0; } int left = depth(root.left); int right = depth(root.right); return Math.max(left, right) + 1; } }