力扣104 求二叉樹的最大深度

力扣104 求二叉樹的最大深度

題目：

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

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

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

示例

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

解題思路：

要求一顆二叉樹的最大深度我們遞歸遍歷這顆二叉樹的左子樹與右子樹分別求得左子樹與右子樹的高度並返回其中的最大值最後再加上1就是這顆二叉樹的最大深度。

代碼：

/**
 * 求一顆二叉樹的最大深度，就看這棵二叉樹的左子樹與右子樹的深度哪個最大，取這兩者的最大值再加1
 * 加1就是加的根節點的這一層
 */
public class MaxDepthTree {
    //1.首先定義二叉樹的節點類
    public static class TreeNode{
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }
    //2.定義一個方法取出以root為根節點的最大的高度
    public static int maxDepth(TreeNode root){
        //2.1如果根節點為空說明此樹的高度為0
        if (root == null) {
            return 0;
        }
        //2.2遞歸左子樹，遞歸右子樹並返回這兩顆子樹的最大值再加1
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }
}