leetcode 988 Smallest String Starting From Leaf解题笔记
- 一个二叉树， 里面每个节点的值是一个整数，表示一个字符串
- 对于所有从叶节点到根节点的路径， 找到最小的路径字符串 （lexicographically smallest string）
- 如果一个字符串是另外一个字符串的前缀， 那么那个前缀是更小的
解题思路分析
- 这个题目和之前的很多题目一样， 需要做bottom up 遍历， 也就是从叶节点遍历
- 对于bottom up 遍历， 通常我们需要做递归的post order从下向上遍历，
- 由于只需要返回一个最小的值， 那么对于任何一个节点， 我们都只需要取当前的最小值， 因为每个节点向上的值都是固定的
区别只在于子节点上的路径， 所以，对于任意一个节点，都从子节点中取最小值
Read full article from leetcode 988 Smallest String Starting From Leaf解题笔记
No comments:
Post a Comment