作者JIWP (神楽めあ的錢包)
標題Re: [閒聊] 每日leetcode
時間2024-04-17 18:49:19
※ 引述《sustainer123 (caster )》之銘言：
: ※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: : https://leetcode.com/problems/smallest-string-starting-from-leaf/description/
: : 988. Smallest String Starting From Leaf
: : 給你一個val範圍在 [0:25] 的二元樹，這些val分別對應 [a:z]，找出從葉子節點到跟
: : 節點路徑表示的最小字典順序字串。
思路 :
一開始以為只要長度比較短就比較小
沒注意到一樣的prefix，搞了好久
思路就dfs去找，到leaf就去比較
對你版大神應該很簡單
golang code
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func smallestFromLeaf(root *TreeNode) string {
ans := []byte{}
now := []byte{}
dfs(&ans, root, &now)
return string(ans)
}
func dfs(ans *[]byte, node *TreeNode, now *[]byte) {
if node == nil {
return
}
(*now) = append([]byte{byte(node.Val + 97)}, (*now)...)
if node.Left == nil && node.Right == nil {
if len(*ans) == 0 || string(*ans) > string(*now) {
(*ans) = make([]byte, len(*now))
copy(*ans, *now)
}
(*now) = (*now)[1:]
return
}
dfs(ans, node.Left, now)
dfs(ans, node.Right, now)
(*now) = (*now)[1:]
}
--
※ 發信站: 批踢踢實業坊(ptt.org.tw), 來自: 42.73.121.212 (臺灣)
※ 文章網址: https://ptt.org.tw/Marginalman/M.1713350961.A.C3F
→ oinishere: 轉職成功了沒 04/17 18:54
→ digua: 大師 04/17 18:54
推 sustainer123: 大師 04/17 18:56