力扣(LeetCode)543

stormjun 發(fā)布于2019-08-16 14:18 / 1784人閱讀

摘要：一棵二叉樹的直徑長度是任意兩個結(jié)點路徑長度中的最大值。這條路徑可能穿過根結(jié)點。注意兩結(jié)點之間的路徑長度是以它們之間邊的數(shù)目表示。

題目地址：
https://leetcode-cn.com/probl...
題目描述：
給定一棵二叉樹，你需要計算它的直徑長度。一棵二叉樹的直徑長度是任意兩個結(jié)點路徑長度中的最大值。這條路徑可能穿過根結(jié)點。

示例 :
給定二叉樹

返回 3, 它的長度是路徑 [4,2,1,3] 或者 [5,2,1,3]。

注意：兩結(jié)點之間的路徑長度是以它們之間邊的數(shù)目表示。

解答：
這一題就是找到每個節(jié)點的深度(等于max(左節(jié)點深度,右節(jié)點深度)+1)，因為穿過任意一個節(jié)點的
直徑，為這個節(jié)點左子樹的深度+右子樹的深度。因此只需要計算出每個節(jié)點深度，就可以得到穿過
某節(jié)點的直徑。因此得到深度之后可以選擇利用dfs深度優(yōu)先搜索來找到答案，也可以在求深度的時候
就直接計算，然后保存在hashmap中。
java ac代碼：

/**
 * 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) {
        if(root == null)return 0;
        HashMap map = new HashMap(500);
        height(root,map);
        int ans = 0;
        for(Map.Entry entry:map.entrySet())
            ans = Math.max(ans,entry.getValue());
        return ans;
        
    }
    public int height(TreeNode root,HashMapmap)
    {
        if(root == null)return 0;
        int left = height(root.left,map);
        int right = height(root.right,map);
        int ans = left + right;
        map.put(root,ans);
        return Math.max(left,right)+1;
    }
}