Minimum Depth of Binary Tree

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.

提示	解題應用
Tree	樹的遍歷方式
DepthFirstSearch	PostOrderTravel

Default:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {

}

解答思路:

一般來說題目所給的通常是要你找出二元樹的最大深度，不過此題卻你要找的是最小深度，而最小深度要注意的是如果是從最大深度來做修改，那麼對於左右子節點若其一為nil，並不表示這就是最小深度，因為最小深度要找的是從存在的樹根中尋找最短的，所以在做遞回後序遍歷時，原本碰上nil節點回傳該節點的深度-1改為一個32位元int的最大值，如此一來就可以直接拿來做比較，也不會受到nil節點的影響了(因為一定不是最小)。

程式碼解說:

(此題思路有修正，建議看完直接拉到最底下參考修正的部分)

除了在最一開始root根節點為nil時要回傳0之外，其餘的nil值一律回傳最大值方便後續比較，而存在節點的左右子節點就一樣分別做遞回，如果其中一個子樹最小深度不是最大值(該子樹存在)，就只要直接與另一個子樹做比較，就算比較的子樹不存在也會因為回傳的值是極大值而傳回原本比較小且存在的子樹深度，而如果是兩個子樹都存在的情況也不需要再加判斷式，因為原本就是在做最小值的比較，而最後如果兩左右子節點都不存在，才回傳該節點的深度。

var maxRowL int
var maxRowR int
if node == nil {
	return math.MaxInt32
}
maxRowL = postOrderTravel(node.Left, maxRow+1)
maxRowR = postOrderTravel(node.Right, maxRow+1)
if maxRowL != math.MaxInt32 && maxRowL <= maxRowR {
	return maxRowL
} else if maxRowR != math.MaxInt32 && maxRowR <= maxRowL {
	return maxRowR
}
return maxRow

完整程式碼:

func postOrderTravel(node *TreeNode, maxRow int) int {
	var maxRowL int
	var maxRowR int
	if node == nil {
		return math.MaxInt32
	}
	maxRowL = postOrderTravel(node.Left, maxRow+1)
	maxRowR = postOrderTravel(node.Right, maxRow+1)
	if maxRowL != math.MaxInt32 && maxRowL <= maxRowR {
		return maxRowL
	} else if maxRowR != math.MaxInt32 && maxRowR <= maxRowL {
		return maxRowR
	}
	return maxRow
}
func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return postOrderTravel(root, 1)
}

總結:

在找二元樹的最小深度時，如果是從最大深度來做修改，注意若其一子節點為nil，並不表示其為最小深度，因為最小深度要找的是從存在樹根中尋找最短的，所以在做遞回後序遍歷時，原本碰上nil節點回傳該節點的深度-1改為一個32位元int的最大值，如此一來就會回傳比較小且存在的另一個子樹最小深度。

修正:

主要是不需要用極大值、極小值的方式判斷路徑，直接從節點判斷左右子節點是否存在，再考慮需不需要遍歷該子節點，如此一來就可以省去非常多的麻煩，大多數關於樹的遍歷都可以用此方式處理。

func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return preOrderTravel(root, 0)
}
func preOrderTravel(node *TreeNode, maxRow int) int {
	if node.Left == nil && node.Right == nil {
		return maxRow + 1
	} else if node.Left == nil {
		return preOrderTravel(node.Right, maxRow+1)
	} else if node.Right == nil {
		return preOrderTravel(node.Left, maxRow+1)
	}
	maxRowL := preOrderTravel(node.Left, maxRow+1)
	maxRowR := preOrderTravel(node.Right, maxRow+1)
	if maxRowL < maxRowR {
		return maxRowL
	}
	return maxRowR
}