二叉樹的最大深度

給定一個二叉樹，找出其最大深度。

二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

說明: 葉子節點是指沒有子節點的節點。

示例：
給定二叉樹 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

通過此題掌握樹的運用

題目分析：求二叉樹的深度；

大家可以瀏覽二叉樹的基本概念一覽來進一步的理解二叉樹；

我們同樣是利用遞歸的方法來解決此題，根結點不為空，我們就遞歸遍歷左子樹和右子樹，看哪一個子樹的層數更多，最後直至遍歷到葉子結點；

運用一條語句技巧性的實現：return nleft > nright ? nleft + 1 : nright + 1;

以這棵二叉樹為例：

    3
   / \
  9  20
    /  \
   15   7

1.此樹非空

2.遞歸遍歷此樹的左子樹：左子樹非空；左子樹的左子樹和右子樹都為空，則都返回0，進行判斷，0 == 0，這此樹的左子樹這邊返回0 + 1 = 1；

3.遞歸遍歷此樹的右子樹：右子樹非空；右子樹的左子樹和右子樹非空；遞歸遍歷右子樹的左子樹和右子樹的右子樹；右子樹的左子樹的左子樹和右子樹為空，返回0，右子樹的右子樹的左子樹和右子樹為空，返回0，進行判斷，0 == 0，則此樹的右子樹的左子樹和右子樹返回 0 + 1 = 1，進行判斷 1 == 1，則此樹的右子樹這邊返回 1 + 1 = 2；

4.比較左子樹和右子樹，1 < 2，則此樹返回2 + 1 = 3，則此樹的深度即層數就為3.

其實此方法的主要思想就是：只要遞歸遍歷一直到此樹的葉子結點，最後只要從葉子結點開始一直向根結點回溯並+1，結果就是回溯經過的路徑長度+1.

代碼實現：

 1 public static class TreeNode
 2     {
 3         int data;
 4         TreeNode left;
 5         TreeNode right;
 6         TreeNode(int val)
 7         {
 8             data = val;
 9         }
10     }
11 
12     public int maxDepth(TreeNode root)
13     {
14         if (root == null)
15             return 0;
16 
17         int nleft = maxDepth(root.left);
18         int nright = maxDepth(root.right);
19 
20         return nleft > nright ? nleft + 1 : nright + 1;
21     }

主函數：

 1  public static void main(String[] args)
 2     {
 3         TreeNode p = new TreeNode(1);
 4         p.left = new TreeNode(2);
 5         p.right = new TreeNode(3);
 6         p.left.left = null;
 7         p.left.right = null;
 8         p.right.left = new TreeNode(4);
 9         p.right.right = new TreeNode(5);
10 
11         Tree1 t = new Tree1();
12         System.out.println(t.maxDepth(p));
13     }

運行結果：

3