Diameter of Binary Tree
二叉树周长, 找到最长的一条路径在二叉树上. 这个路径不一定过root, 也不一定在某节点两侧. 所以我先要写一个找到depth的方法. 然后找每个节点的左边和右边. 最后把所有的结果取max.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
/** * 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); } } |