543. 二叉樹的直徑

描述

給定一棵二叉樹，你需要計算它的直徑長度。一棵二叉樹的直徑長度是任意兩個結點路徑長度中的最大值。這條路徑可能穿過也可能不穿過根結點。

示例 :
給定二叉樹

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

注意：兩結點之間的路徑長度是以它們之間邊的數目表示。

思路

首先我們知道一條路徑的長度為該路徑經過的節點數減一，所以求直徑（即求路徑長度的最大值）等效于求路徑經過節點數的最大值減一。

目的：自上而下，深度優先遍歷，得到每一個節點的長度，左右子節點兩邊的長度之和加一即為其父節點的“長度”，以此遍歷得到每個節點的“長度”，維護一個變量，實時更新最長的“長度”，并返回該節點為根的子樹的深度。其中，basecase:if (node == null) return 0;
(任意一條路徑均可以被看作由某個節點為起點，從其左兒子和右兒子向下遍歷的路徑拼接得到 -->遞歸)

class Solution {int ans;public int diameterOfBinaryTree(TreeNode root) {ans = 1;depth(root);return ans - 1;}public int depth(TreeNode node) {if (node == null) return 0; // 訪問到空節點了，返回0--->basecaseint L = depth(node.left); // 左兒子為根的子樹的深度int R = depth(node.right); // 右兒子為根的子樹的深度ans = Math.max(ans, L+R+1); // 計算d_node即L+R+1 并更新ansreturn Math.max(L, R) + 1; // 返回該節點為根的子樹的深度} }

復雜度分析

• 時間復雜度：O(N)，其中 N 為二叉樹的節點數，即遍歷一棵二叉樹的時間復雜度，每個結點只被訪問一次。

• 空間復雜度：O(Height)，其中Height 為二叉樹的高度。由于遞歸函數在遞歸過程中需要為每一層遞歸函數分配棧空間，所以這里需要額外的空間且該空間取決于遞歸的深度，而遞歸的深度顯然為二叉樹的高度，并且每次遞歸調用的函數里又只用了常數個變量，所以所需空間復雜度為 O(Height) 。

總結

以上是生活随笔為你收集整理的543. 二叉树的直径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。