《劍指offer》之二叉樹的深度

• 2020 年 3 月 13 日
• 筆記

前言

我們今天接著來看一道關於二叉樹的演算法題，關於二叉樹的深度。

題目

輸入一棵二叉樹，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。

分析

求該樹的深度，主要就是看最長路徑。比如下圖的深度為5，最長的路徑為34，99，35，64，77

那應該怎麼做？這裡用遞歸，如果當前節點沒有左右節點，就返回當前節點，如果有左右節點，就返回左右節點的，比較左節點和右節點的深度，誰的深度大就返回那個。這樣就可以獲得樹的最大深度啦。

解法

public int TreeDepth(TreeNode root) {          if(root==null){              return 0;          }            int left=TreeDepth(root.left);          int right=TreeDepth(root.right);          if(left>right){              return left+1;          }          return right+1;        }

上面主要注意的是left+1 和right+1;為什麼要加一呢，因為我們遞歸的出口是當前節點為null ,返回0，為1個節點的話返回1.

測試

測試main方法

public static void main(String[] args) {          TreeNode root =new TreeNode(34);          root.left=new TreeNode(23);          root.right=new TreeNode(99);          root.left.left=new TreeNode(1);          root.left.right=new TreeNode(27);          root.right.left=new TreeNode(35);          root.right.left.right=new TreeNode(64);          root.right.left.right.right=new TreeNode(77);          TreeOperation.show(root);          Solution solution= new Solution();          System.out.println(solution.TreeDepth(root));      }