[Golang]力扣Leetcode—初级算法—树—二叉树的最大深度 [Golang]力扣Leetcode—初级算法—

题目：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明：叶子节点是指没有子节点的节点。
链接：力扣Leetcode—初级算法—树—二叉树的最大深度.
示例：

给定二叉树 [3，9，20，null，null，15，7]
??
????3
???/??\
??9???20
?????/??\
????15???7
??
返回它的最大深度 3 。

标签：树、深度优先搜索、广度优先搜索、二叉树
【[Golang]力扣Leetcode—初级算法—树—二叉树的最大深度】思路：找出树中深度最大的子树，把他看成一个新树，再继续从新树中找出深度较大者。一直递归到临界点，即当树根为空时，说明树不存在，深度为 0，递归结束，在其中每递归一次，深度就+1。
主要Go代码如下：

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

提交截图：

文章图片

官方解答：官方用了递归 DFS（深度优先搜索 Depth-First-Search），树的最大深度 = 根节点的高度（根本身为 1 ）+ 左右子树的最大深度中的较大者。而左右子树最大深度怎么求呢？以左子树为例，把它看成新的一棵树，那么它的最大深度就是：根节点的高度（根本身为 1 ）+ 左右子树的最大深度中的较大者。这样就发现递归的所在点了。到临界点即当树根为空时，说明树不存在，深度为 0，递归结束。

/** * 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 } return max(maxDepth(root.Left), maxDepth(root.Right)) + 1 }func max(a,b int)int { if a > b { return a } return b }