题目描述
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]示例 2：
输入：root = [1]
输出：["1"]提示：
- 树中节点的数目在范围
[1, 100]内 -100 <= Node.val <= 100
思路
本题要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。
递归三部曲：
- 确定递归函数的参数和返回值。要传入根节点，记录每一条路径的path，和存放结果集的result，这里递归不需要返回值。
- 确定终止条件。本题没有必要遍历到空节点才结束，只需要遍历到叶子结点就可以结束了。当cur不为空，且其左右孩子都为空的时候，就找到叶子节点了。
- 确定单层递归的逻辑。因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中。然后是递归和回溯的过程，递归时需要先判断cur是否为空，如果为空就不进行下一层递归了。递归之后就要回溯，因为path不能一直加入节点，它还要删节点，然后才能加入新的节点。
代码
C++版：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:// 递归法// path存放路径,result存放结果集void traversal(TreeNode* n,vector<int>& path,vector<string>& result){// 中path.push_back(n->val);// 终止条件，到达叶子节点if(n->left==NULL && n->right==NULL){string sPath;for (int i = 0; i < path.size() - 1; i++) {sPath += to_string(path[i]);sPath += "->";}sPath += to_string(path[path.size() - 1]);result.push_back(sPath);return; }// 左if(n->left){traversal(n->left,path,result);path.pop_back(); // 回溯}// 右if(n->right){traversal(n->right,path,result);path.pop_back(); // 回溯}}vector<string> binaryTreePaths(TreeNode* root) {vector<int> path;vector<string> result;if(root==NULL) return result;traversal(root,path,result);return result;}
};Python版：
python"># 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 traversal(self, cur, path, result):path.append(cur.val) # 中if not cur.left and not cur.right: # 到达叶子节点sPath = '->'.join(map(str, path))result.append(sPath)returnif cur.left: # 左self.traversal(cur.left, path, result)path.pop() # 回溯if cur.right: # 右self.traversal(cur.right, path, result)path.pop() # 回溯def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:result = []path = []if not root:return resultself.traversal(root, path, result)return result需要注意的地方
1.如果使用迭代法来解决本题，除了模拟递归需要一个栈，同时还需要一个栈来存放对应的遍历路径。
