描述
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]示例 2：
输入：root = [1]
输出：["1"]提示：
- 树中节点的数目在范围
[1, 100]内 -100 <= Node.val <= 100
题解
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:
void helper(TreeNode* cur, vector<int>& path, vector<string>& result){
path.push_back(cur->val);
if(!cur->left && !cur->right){
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);
}
if(cur->left){
helper(cur->left, path, result);
path.pop_back(); // 回溯
}
if(cur->right){
helper(cur->right, path, result);
path.pop_back();
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
vector<int> path;
if(!root) return result;
helper(root, path, result);
return result;
}
};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 helper(self, cur: TreeNode, path: str, result: List[str]) -> None:
path += str(cur.val)
# 若当前节点为叶子结点，直接输出
if not cur.left and not cur.right:
result.append(path)
if cur.left:
self.helper(cur.left, path + '->', result)
if cur.right:
self.helper(cur.right, path + '->', result)
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
path = ''
result = []
if not root:
return result
self.helper(root, path, result)
return result
