1.題目：

求任意一顆二叉樹(shù)最長(zhǎng)路徑長(zhǎng)度

樣例:如下所示

圖一樹(shù)的最長(zhǎng)路徑長(zhǎng)度為4，圖二的最長(zhǎng)路徑長(zhǎng)度為7，圖一最長(zhǎng)路徑經(jīng)過(guò)根節(jié)點(diǎn)，頂點(diǎn)為1，圖二不經(jīng)過(guò)，頂點(diǎn)為3

2.思路

樹(shù)中任意兩個(gè)節(jié)點(diǎn)之間，連接起來(lái)的路徑最長(zhǎng)。方法就是求出每個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的高度，兩者相加就是當(dāng)前節(jié)點(diǎn)的最長(zhǎng)路徑，然后比較每個(gè)節(jié)點(diǎn)的最長(zhǎng)路徑，最大的就是結(jié)果

3.實(shí)現(xiàn)方法

定義一個(gè)靜態(tài)變量MaxLength記錄每一步最大長(zhǎng)度，采取前序遍歷來(lái)遍歷每一個(gè)節(jié)點(diǎn)，在遍歷過(guò)程中，對(duì)當(dāng)前節(jié)點(diǎn)的最長(zhǎng)路徑進(jìn)行比較，對(duì)于每一個(gè)節(jié)點(diǎn)最長(zhǎng)路徑求法，先求出它左子樹(shù)和右子樹(shù)的高度(節(jié)點(diǎn)數(shù)最多的路徑),然后相加即為當(dāng)前節(jié)點(diǎn)最長(zhǎng)路徑

代碼如下：

static Integer MaxLength=0;//記錄最長(zhǎng)路徑 //遍歷整棵樹(shù)，得到最長(zhǎng)路徑 public void getLength(TreeNode t){if(t!=null){MaxLength=Math.max(LengthTree(t),MaxLength);getLength(t.lchild);getLength(t.rchild);} } //得到當(dāng)前節(jié)點(diǎn)的最長(zhǎng)路徑 public int LengthTree(TreeNode t){if (t==null)return 0;int left=heighTree(t.lchild);int right=heighTree(t.rchild);int CurMax=left+right;return CurMax; } //求二叉樹(shù)最大高度 public int heighTree(TreeNode t){if (t==null)return 0;elsereturn Math.max(heighTree(t.lchild),heighTree(t.rchild))+1; }

4.結(jié)果

圖一樹(shù)最長(zhǎng)路徑

圖二最長(zhǎng)路徑結(jié)果

總結(jié)

以上是生活随笔為你收集整理的求二叉树最长路径长度和的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。