文章目录

前言

一、问题

二、思路

1.基于深度优先遍历

2.代码实现

总结

---

前言

二叉树为程序员面试的常见问题，本文将对leetcode中257二叉树的所有路径进行讲解。

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、问题

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

   1  /   \ 2     3  \   5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

二、思路

1.基于深度优先遍历

问题为将每个叶子结点到根节点的路径都提取出来，存到一个list中。最先想到的方法就是深度优先遍历，遍历到叶子结点时，将路径保存，然后继续遍历，直到遍历完成整棵树。需要处理的就是当节点为叶子结点和非叶子节点时的区别。

当节点为叶子结点时，将当前节点的值加入到path中，此时到达此叶子结点的path已经生成，即可将path保存到list中。

当节点为非叶子结点，将当前节点的值加入path中，然后递归的继续遍历节点的子节点。当节点不存在是返回空，跳出递归。

2.代码实现

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def binaryTreePaths(self, root: TreeNode) -> List[str]: def construct_paths(root, path): if not root:return path += str(root.val) if not root.left and not root.right: #叶子结点 paths.append(path) else: path += '->' construct_paths(root.left, path) construct_paths(root.right, path) paths = [] construct_paths(root, '') return paths

---

总结

树相关的算法题，大多都可采用递归的思路来解决，因为树的结构天生比较适合递归。另外对于递归思想的精通也对解决此类算法也相当重要。