首先我采用了dfs，但是我的方法有点麻烦。
方法一：dfs
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> res; if(root == NULL) return res; string str = std::to_string(root->val); if(root->left != NULL || root->right != NULL){ dfs(root->left, res, str); dfs(root->right, res, str); } else res.push_back(str); return res; } void dfs(TreeNode* root, vector<string>& res, string str){ if(root == NULL) return; str += "->" + std::to_string(root->val); if(root->left == NULL && root->right == NULL){ res.push_back(str); return ; } dfs(root->left, res, str); dfs(root->right, res, str); }};然后我参照别人的dfs，重新用Python写了一遍，简化了一些步骤。
下面是dfs的简洁版本：
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def binaryTreePaths(self, root): if not root: return [] res = [] self.dfs(root, res, "") return res; def dfs(self, root, res, ls): if not root.left and not root.right: res.append(ls+str(root.val)); return res if root.left: self.dfs(root.left, res, ls+str(root.val)+"->") if root.right: self.dfs(root.right, res, ls+str(root.val)+"->")非递归版的dfs，类似于二叉树的前序遍历，使用stack：
class Solution(object): def binaryTreePaths(self, root): res = [] if not root: return res self.dfs(root, res) return res; def dfs(self, root, res): if not root: return [] stack = [(root, "")] while stack: node, ls = stack.pop() if not node.left and not node.right: res.append(ls+str(node.val)) if node.right: stack.append((node.right, ls+str(node.val)+"->")) if node.left: stack.append((node.left, ls+str(node.val)+"->")) return res方法二：采用广度优先BFS，使用队列：
class Solution(object): def binaryTreePaths(self, root): res = [] if not root: return res self.bfs(root, res) return res; def bfs(self, root, res): if not root: return [] queue = collections.deque([(root, "")]) while queue: node, ls = queue.popleft() if not node.left and not node.right: res.append(ls+str(node.val)) if node.left: queue.append((node.left, ls+str(node.val)+"->")) if node.right: queue.append((node.right, ls+str(node.val)+"->")) return res新闻热点
疑难解答
