543 Diameter of Binary Tree
1. Question
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.
2. Implementation
(1) DFS Recursion
思路: 这题其实和124找max path sum一样,基本的步骤都是先用postorder traversal 找出当前node的left path的信息,和right path的信息,然后用一个变量找出当前的信息加上左右两边信息的总和 与 当前已知的最大信息之间的较大者。返回的值则是当前的信息(节点的个数或者节点的值) 加上左右两边信息较大的一方
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
int[] diameter = new int[1];
getDiameterOfTree(root, diameter);
return diameter[0];
}
public int getDiameterOfTree(TreeNode node, int[] diameter) {
if (node == null) {
return 0;
}
int leftDiameter = getDiameterOfTree(node.left, diameter);
int rightDiameter = getDiameterOfTree(node.right, diameter);
diameter[0] = Math.max(diameter[0], leftDiameter + rightDiameter);
return 1 + Math.max(leftDiameter, rightDiameter);
}
}
3. Time & Space Complexity
DFS Recursion: 时间复杂度O(n), n为树node的个数, 空间复杂度O(n)
Last updated
Was this helpful?