2021-03-21：给定一棵二叉树的头节点head，求以head为头的树中，最小深度是多少？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了2021-03-21：给定一棵二叉树的头节点head，求以head为头的树中，最小深度是多少？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1575字，纯文字阅读大概需要3分钟。

内容图文

2021-03-21：给定一棵二叉树的头节点head，求以head为头的树中，最小深度是多少？

福大大 答案2021-03-21：

1.递归。
2.莫里斯遍历。

代码用golang编写，代码如下：

package main

import "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代码
评论

内容总结

以上是互联网集市为您收集整理的2021-03-21：给定一棵二叉树的头节点head，求以head为头的树中，最小深度是多少？全部内容，希望文章能够帮你解决2021-03-21：给定一棵二叉树的头节点head，求以head为头的树中，最小深度是多少？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---