Diameter of Binary Tree
二叉树周长, 找到最长的一条路径在二叉树上. 这个路径不一定过root, 也不一定在某节点两侧. 所以我先要写一个找到depth的方法. 然后找每个节点的左边和右边. 最后把所有的结果取max.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int res = Integer.MIN_VALUE;
public int diameterOfBinaryTree(TreeNode root) {
if(root == null)
return 0;
int left = depth(root.left);
int right = depth(root.right);
res = Math.max(left+right, res); // current
res = Math.max(diameterOfBinaryTree(root.left), res); //current's left
res = Math.max(diameterOfBinaryTree(root.right), res); //current's right
return res;
}
public int depth(TreeNode root){
if(root == null){
return 0;
}
int left = 1 + depth(root.left);
int right = 1 + depth(root.right);
return Math.max(left, right);
}
}