111. Minimum Depth of Binary Tree
https://leetcode.com/problems/minimum-depth-of-binary-tree/
題意
尋找這棵樹最小的節點，他的深度為何？
解題思路
這次的題目與 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 的筆記本 留言，順手給我個讚吧！你的讚將成為我持續更新的動力，感謝你的閱讀，讓我們一起學習成為更好的自己。