P14 二叉树最小深度(深度优先和广度优先)

客官°小女子只卖身不卖艺 2023-01-23 13:50 128阅读 0赞

# 一、深度优先 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70]

// 时间O(N^2)空间O(1)
    func MinDeepByRecursion(tree *Node) float64 { 
    	// 达到叶子节点
    	if tree.Left == nil && tree.Right == nil { 
    		return 1
    	}
    	var ldeep, rdeep float64 = math.MaxFloat64, math.MaxFloat64
    	if tree.Left != nil {  // 如果有左节点，算出左节点的深度
    		ldeep = Deep(tree.Left)
    	}
    	if tree.Right != nil {  // 如果有右节点，算出右节点的深度
    		rdeep = Deep(tree.Right)
    	}
    	// 返回当前左右节点的最小深度，并加上自己这一层
    	return math.Min(ldeep, rdeep) + 1
    }

# 二、广度优先 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70 1]

// 时间O(N)空间O(N)
    func MinDeepByIteration(tree *Node) (deep int) { 
    	if tree == nil { 
    		return
    	}
    	deep = 1                     // 初始深度
    	var currLen, afterLen = 1, 0 // 当前深度节点数，当前深度子节点数
    	queue := make(chan *Node, 10)
    	queue <- tree
    
    	for len(queue) > 0 { 
    		curr := <-queue
    		// 是叶子，返回当前深度
    		if curr.Left == nil && curr.Right == nil { 
    			return
    		}
    		if curr.Left != nil { 
    			afterLen++
    			queue <- curr.Left
    		}
    		if curr.Right != nil { 
    			afterLen++
    			queue <- curr.Right
    		}
    
    		// 消耗一个当前深度节点
    		// 若深度消耗完毕,往下一层消耗
    		if currLen--; currLen == 0 { 
    			deep++
    			currLen = afterLen
    			afterLen = 0 // 置为0
    		}
    	}
    	return -1
    }

# 三、测试 #

func main() { 
    	tt := NewTree()
    	fmt.Println(MinDeepByRecursion(tt))
    	fmt.Println(MinDeepByIteration(tt))
    }
    
    type Node struct { 
    	Value int
    	Left  *Node
    	Right *Node
    }
    
    func NewTree() *Node { 
    	// 第四层
    	left42 := &Node{ Value: 7}
    	// 第三层
    	left31 := &Node{ Value: 4}
    	right31 := &Node{ Value: 5}
    	left32 := &Node{ Value: 6, Left: left42}
    	// 第二层
    	left21 := &Node{ Value: 2, Left: left31, Right: right31}
    	right21 := &Node{ Value: 3, Left: left32}
    	return &Node{ Value: 1, Left: left21, Right: right21}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70]: /images/20221004/16d7ef7fd61c4e17b6611495a2f0f1c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70 1]: /images/20221004/ae355f87b4074afab42344a3a27b4bd2.png