111. Minimum Depth of Binary Tree
https://leetcode.com/problems/minimum-depth-of-binary-tree/
Easy
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: 2
Example 2:
Input: root = [2,null,3,null,4,null,5,null,6] Output: 5
Constraints:
- The number of nodes in the tree is in the range
[0, 105]. -1000 <= Node.val <= 1000
題意
尋找這棵樹最小的節點，他的深度為何？
解題思路
這次的題目與 104 Maximum Depth of Binary Tree 相似，這次當然也要使用不同的思路解題，這次就使用迴圈的方式解題吧。
我們每一次迴圈，就搜尋一次當前 i 層是不是有 Left 與 Right 節點為空的節點，如果有就當作是最小深度回傳，如果沒有就將該層丟入 queue 內，在下一層再取出檢查。
- 宣告一個 queue ，並且把 root 塞入。
- 宣告一個 深度 變數，用於記錄目前深度為多少。
- 開始 while 循環，只要 queue 的長度不為 0 ，就一直循環。
- 從 queue 取出一個 node ，並且檢查是否左右節點都為空，如果是就返回當前深度，如果不是就將左右兩個節點塞入 queue 中，讓第三步循環下去。
原始碼
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
depth := 0
queue := []*TreeNode{root}
for len(queue) > 0 {
depth++
length := len(queue)
for i := 0; i < length; i++ {
node := queue[0]
if node.Left == nil && node.Right == nil {
return depth
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
queue = queue[1:]
}
}
return depth
}
結尾
你有更好或更簡單的解決方案嗎？
歡迎到我的 Facebook Alan 的筆記本 留言，順手給我個讚吧！你的讚將成為我持續更新的動力，感謝你的閱讀，讓我們一起學習成為更好的自己。
