1.問題描述

????????給你一棵二叉樹的根節點，返回該樹的?直徑?。

????????二叉樹的?直徑?是指樹中任意兩個節點之間最長路徑的?長度?。這條路徑可能經過也可能不經過根節點?root?。

????????兩節點之間路徑的?長度?由它們之間邊數表示。

????????示例1

輸入：root = [1,2,3,4,5]
輸出：3
解釋：3 ，取路徑 [4,2,1,3] 或 [5,2,1,3] 的長度。

? ? ? ? 示例2?

輸入：root = [1,2]
輸出：1

????????提示

• 樹中節點數目在范圍?[1, 104]?內
• -100 <= Node.val <= 100

????????難度等級

? ? ? ? ? ? ? ? 簡單

????????題目鏈接

????????????????二叉樹的直徑

2.解題思路

? ? ? ? 這道題目是要求二叉樹的直徑，這道題如果搞清楚了各個概念直接的關系，就會變得非常簡單，我們一起來看一下。

? ? ? ? 首先，我們要求的是二叉樹的直徑，根據題目給的定義，二叉樹的直徑是二叉樹中任意兩個節點之間最大路徑的長度。所以我們的問題就是找到最大的路徑長度，而路徑長度=經過的節點數-1。所以，我們可以把問題轉化為求經過最多的節點數。

? ? ? ? 我們要求經過最多的節點數，怎么樣才能經過盡可能多的節點數呢？那肯定要最深的節點一直到根節點再轉向，轉向到另外一棵子樹的最深節點處。但是這里有一個問題，就是到根節點轉向，不一定就是最多的節點數，可能另外一棵子樹沒有多少節點呢？反而可能是在某一個節點轉向之后，節點數更多。所以，我們的解決辦法就是求出以每一個節點為根節點，從左最深處到右最深處的節點數，然后取最大值。

? ? ? ? 這里要明確一點，要從左最深處到右最深處，那我們就要分別求出左右兩顆子樹的深度。那這個問題就被轉化為求最大深度的問題了。

? ? ? ? 我們定義一個變量，用來更新最大節點數。

    //存儲經過的最大節點數int result = 1;

? ? ? ? 遞歸的結束條件是，如果節點為空，直接返回0就可以了。

        //空節點返回0if(node == null){return 0;}

? ? ? ? 然后我們就可以對左右子樹遞歸求深度，然后取左右子樹的最大值+1(這里的+1指加上當前根節點本身)進行返回。

        //左子樹的深度int L = dfs(node.left);//右子樹的深度int R = dfs(node.right);.....return Math.max(L,R) + 1;

? ? ? ? 到這里，我們已經完成了求最大深度的邏輯。但是我們還缺少了求最大節點數的邏輯。到這一步，已經不難了，因為我們前面已經遞歸求了左右子樹的深度，我們只需要將左子樹的深度加上右子樹的深度，再加1，就是以當前節點為根，所可能經過的最大節點數了。這里的+1(是因為要從左最深到右最深，必須經過當前節點，所以要把當前節點也算上)。將以當前節點為根所經過的最大節點數與全局已經記錄的最大節點數進行比較，取最大值即可。

        //更新經過的最大節點數result = Math.max(result,L + R + 1);

? ? ? ? 當我們求完整個樹的深度時，我們的最大節點數也就跟著求出來了。此時，只需要按照定義，將經過的最大節點數-1返回即可。

        dfs(root);//直徑=經過的最大節點數-1return result - 1;

3.代碼展示

/*** 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 {int result = 1;public int diameterOfBinaryTree(TreeNode root) {dfs(root);//直徑=經過的最大節點數-1return result - 1;}public int dfs(TreeNode node){//空節點返回0if(node == null){return 0;}//左子樹的深度int L = dfs(node.left);//右子樹的深度int R = dfs(node.right);//更新經過的最大節點數result = Math.max(result,L + R + 1);return Math.max(L,R) + 1;}
}

4.總結

? ? ? ? 這道題，只需要理清幾個概念直接的關系，就可以將問題簡化成我們曾經做過的求深度問題，這樣問題也就輕松解決了。今天這道題就啰嗦到這，祝大家刷題愉快~