2021-03-21：給定一棵二叉樹的頭節點head，求以head為頭的樹中，最小深度是多少？

福大大 答案2021-03-21：

1.遞迴。

2.莫里斯遍歷。

程式碼用golang編寫，程式碼如下：

package mainimport "fmt"func main() {    head := &TreeNode{}    head.Left = &TreeNode{}    head.Right = &TreeNode{}    head.Right.Right = &TreeNode{}    ret := minHeight1(head)    fmt.Println("1.遞迴:", ret)    ret = minHeight2(head)    fmt.Println("2.莫里斯遍歷：", ret)}//Definition for a binary tree node.type TreeNode struct {    Val   int    Left  *TreeNode    Right *TreeNode}const INT_MAX = int(^uint(0) >> 1)func minHeight1(head *TreeNode) int {    if head == nil {        return 0    }    leftVal := minHeight1(head.Left)    rightVal := minHeight1(head.Right)    return 1 + getMin(leftVal, rightVal)}// 根據morris遍歷改寫func minHeight2(head *TreeNode) int {    if head == nil {        return 0    }    cur := head    var mostRight *TreeNode    curLevel := 0    minHeight := INT_MAX    for cur != nil {        mostRight = cur.Left        if mostRight != nil {            rightBoardSize := 1            for mostRight.Right != nil && mostRight.Right != cur {                rightBoardSize++                mostRight = mostRight.Right            }            if mostRight.Right == nil { // 第一次到達                curLevel++                mostRight.Right = cur                cur = cur.Left                continue            } else { // 第二次到達                if mostRight.Left == nil {                    minHeight = getMin(minHeight, curLevel)                }                curLevel -= rightBoardSize                mostRight.Right = nil            }        } else { // 只有一次到達            curLevel++        }        cur = cur.Right    }    finalRight := 1    cur = head    for cur.Right != nil {        finalRight++        cur = cur.Right    }    if cur.Left == nil && cur.Right == nil {        minHeight = getMin(minHeight, finalRight)    }    return minHeight}func getMin(a int, b int) int {    if a < b {        return a    } else {        return b    }}

執行結果如下：

***

[左神java程式碼](https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class30/Code05_MinHeight.java#L35)