DEV Community
·
Leetcode - 112. 路径和
💡
原文英文，约200词，阅读约需1分钟。
📝
内容提要
使用深度优先遍历判断从根到叶子节点的路径和是否等于目标值。若节点为空返回假，若为叶子节点且值匹配则返回真。时间复杂度为O(N)，空间复杂度为O(H)。
🎯
关键要点
- 使用深度优先遍历判断从根到叶子节点的路径和是否等于目标值。
- 若节点为空返回假，若为叶子节点且值匹配则返回真。
- 时间复杂度为O(N)，空间复杂度为O(H)。
- 步骤包括：检查节点是否为空，检查是否为叶子节点，递归左右子节点。
- 代码实现中，若节点为空返回假，若为叶子节点且目标值匹配则返回真。
- 最坏情况下，可能访问每个节点一次，时间复杂度为O(N)。
- 空间复杂度取决于树的高度，最坏情况下为O(H)。
❓
延伸问答
如何判断从根到叶子节点的路径和是否等于目标值？
使用深度优先遍历，递归检查每个节点，直到找到叶子节点并判断其值是否与目标值匹配。
在路径和问题中，时间复杂度和空间复杂度分别是多少？
时间复杂度为O(N)，空间复杂度为O(H)，其中N是树的节点数，H是树的高度。
如果节点为空，函数会返回什么？
如果节点为空，函数会返回假。
如何实现路径和的递归代码？
代码通过检查节点是否为空、是否为叶子节点，并递归调用左右子节点来实现路径和的判断。
在最坏情况下，算法会访问多少个节点？
在最坏情况下，算法可能会访问每个节点一次，即O(N)。
路径和问题的递归步骤有哪些？
步骤包括检查节点是否为空，检查是否为叶子节点，递归左右子节点。
➡️
