基本信息

  • 题号：257
  • 题厂：脸书，亚麻
  • 难度系数：低


遍历二叉树路径


例如 root = [1,2,3,null,5]
返回 ["1->2->5","1->3"]

就有两条路径，1-2-5 和 1-3，用“->“串联返回 string 就好


解题思路

  • 熟悉套路之后，一眼看出这是 「DFS」查询，当然顺便还需要用到一点 backtrack 逻辑……
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []

        # 创建 dfs 方法 走 recursive 路线……
        def dfs(node, stack):
            # 已知二叉树至少有一个节点，遍历时先将其对应 string 值放入 stack
            stack.append(str(node.val))
            
            # 如果该节点的左右节点均为空，说明路径到头，把 stack 添加到 res 返回
            if not node.left and not node.right:
                res.append("->".join(stack))
                return
            
            # 如果左节点存在，就往左节点深度遍历
            # 当到头返回时，要把 stack 最后一个元素 pop 出来，即：「backtrack 精髓」所在
            if node.left:
                dfs(node.left, stack)
                stack.pop()

            # 同理，如果右节点存在，就往右节点深度遍历
            # 当到头返回时，同样要把 stack 最后一个元素 pop 出来
            if node.right:
                dfs(node.right, stack)
                stack.pop()
            
        dfs(root, [])
        
        return res


Constraints

  • The number of nodes in the tree is in the range [1, 100].
  • -100 <= Node.val <= 100

做题前要和考官讨论会不会有空节点？？？


Big O

  • 时间复杂度：O（n），每个节点走一遍；
  • 空间复杂度：O（logn）。stack 长度巅峰时为二叉树高度。。。。。。



测试

  • 只有一个节点时
  • 左节点为空或右节点为空时。。。。。。

……


总结

  • 这题也可以用 stack 走 iteration 路线，当然本题的考点还是 DFS + backtracking
  • 虽然题意很容易理解，属于基础概念，但 backtracking 是很容易搞混的一种高级思想，所以还是需要经常复习以免遗忘——毕竟是一道涵盖 二叉树 + DFS + backtrack 多重知识考点的经典基础题。。。。。。