一、题目描述

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

提示：

节点总数 <= 10000

二、我的题解

要求树的深度，最直接的想法就是深度优先遍历，遍历一层则层数加1。

深度优先遍历有两种写法：递归、栈

以下代码我使用递归来实现。

思路：

输入 maxDepth 函数的 root 指针

如果 root 为 nil，深度为 0
如果左右孩子都为 nil ，深度为 1
如果左孩子为 nil，返回右孩子的深度 +1；如果右孩子为 nil，返回左孩子的深度 +1
如果左右孩子不为 nil，返回左右孩子较大的深度

遍历到叶子那一层的时候，会返回 1 ，然后每往上一层就加 1，最终返回树的深度。

代码1：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil{
        return 0
    }else if root.Left == nil && root.Right == nil{
        return 1
    }else if root.Left == nil && root.Right != nil{
        return 1 + maxDepth(root.Right)
    }else if root.Right == nil && root.Left != nil{
        return 1 + maxDepth(root.Left)
    }else{
        a := maxDepth(root.Left)
        b := maxDepth(root.Right)
        if a >= b{
            return 1 + a
        }else{
            return 1 + b
        }
    }
}

评判结果：

实际上，上述代码还可以简化：

代码2：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil{
        return 0
    }else{
        a := maxDepth(root.Left)
        b := maxDepth(root.Right)
        if a >= b{
            return 1 + a
        }else{
            return 1 + b
        }
    }
}