一、題目大意
給定一棵二叉樹，你需要計算它的直徑長度，一棵二叉樹的直徑長度是任意兩個結點路徑長度中的最大值，這條路徑可能穿過也可能不穿過根結點，
示例 :
給定二叉樹
1
/ \
2 3
/ \
4 5
回傳 3, 它的長度是路徑 [4,2,1,3] 或者 [5,2,1,3]，
注意：兩結點之間的路徑長度是以它們之間邊的數目表示，
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/diameter-of-binary-tree
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
求二叉樹的直徑，其實就是求根節點左右兩個子樹的深度之和，我們只要對每個節點求出其左右子樹深度之和，這個值作為一個候選值，
三、解題方法
3.1 Java實作
/**
* 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 {
/**
* 用來優化遞回
*/
Map<TreeNode, Integer> map = new HashMap<>();
public int diameterOfBinaryTree(TreeNode root) {
int[] diameter = new int[1];
maxDepth(root, diameter);
return diameter[0];
}
/**
* 求二叉樹的最大深度，而二叉樹的直徑為 左二叉樹深度 + 右二叉樹深度
*/
int maxDepth(TreeNode root, int[] diameter) {
if (root == null) {
return 0;
}
if (map.containsKey(root)) {
return map.get(root);
}
int l = maxDepth(root.left, diameter);
int r = maxDepth(root.right, diameter);
diameter[0] = Math.max(l + r, diameter[0]);
return Math.max(l, r) + 1;
}
}
四、總結小記
- 2022/9/9 馬上中秋節啦
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/506025.html
標籤：其他