二叉树的所有路径（ LeetCode 257 ）
一、题目描述
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的所有路径（ LeetCode 257 ）:https://leetcode-cn.com/problems/binary-tree-paths/submissions/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
// res 存放所有从根节点到叶子节点的路径。
List<String> res = new ArrayList<String>();
// 边界情况处理
if (root == null) {
return res;
}
// 设置一个队列 nodeQueue，用来遍历存储二叉树中的元素
Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
// 设置一个队列 pathQueue，用来记录路径
Queue<String> pathQueue = new LinkedList<String>();
// Queue 中 add() 和 offer()都是用来向队列添加一个元素
// 在容量已满的情况下，add() 方法会抛出 IllegalStateException 异常，offer() 方法只会返回 false
// nodeQueue 队列添加二叉树的根节点
nodeQueue.offer(root);
// pathQueue 队列添加二叉树的根节点的值
pathQueue.offer(Integer.toString(root.val));
// 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
while (!nodeQueue.isEmpty()) {
// 从 nodeQueue 中取出一个节点，此时，nodeQueue 已经抛出了这个节点
TreeNode node = nodeQueue.poll();
// 从 pathQueue 中取出一个元素，此时，nodeQueue 已经抛出了这个元素
String path = pathQueue.poll();
// 判断当前节点的左子节点和右子节点是否存在
// 即判定当前节点是否是叶子节点，如果是叶子节点，那么就找到了一条路径
if (node.left == null && node.right == null) {
// 把这条路径添加到结果数组中
res.add(path);
} else {
// 判断当前节点的左子节点是否存在，如果存在，顺着这个节点去寻找叶子节点
if (node.left != null) {
// nodeQueue 队列添加这个存在的左子节点
nodeQueue.offer(node.left);
// 接下来，需要把这个节点加入到 path 这条路径中
StringBuilder strB = new StringBuilder(path);
// 添加 ->
strB.append("->");
// 添加当前节点的值
strB.append(node.left.val);
// node.left 成功添加到 path 这条路径中，形成了 newPath
String newPath = strB.toString();
// pathQueue 队列记录这条路径
pathQueue.offer(newPath);
}
if (node.right != null) {
// nodeQueue 队列添加这个存在的左子节点
nodeQueue.offer(node.right);
// 接下来，需要把这个节点加入到 path 这条路径中
StringBuilder strB = new StringBuilder(path);
// 添加 ->
strB.append("->");
// 添加当前节点的值
strB.append(node.right.val);
// node.left 成功添加到 path 这条路径中，形成了 newPath
String newPath = strB.toString();
// pathQueue 队列记录这条路径
pathQueue.offer(newPath);
}
}
}
// 返回 res
return res;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的所有路径（ LeetCode 257 ）:https://leetcode-cn.com/problems/binary-tree-paths/submissions/
class Solution
{
public:
vector<string> binaryTreePaths(TreeNode* root)
{
// res 存放所有从根节点到叶子节点的路径。
vector<string> res;
// 边界情况处理
if (root == NULL)
{
return res;
}
// 设置一个队列 nodeQueue，用来遍历存储二叉树中的元素
queue<TreeNode*> nodeQueue;
// 设置一个队列 pathQueue，用来记录路径
queue<string> pathQueue;
// Queue 中 add() 和 offer()都是用来向队列添加一个元素
// 在容量已满的情况下，add() 方法会抛出 IllegalStateException 异常，offer() 方法只会返回 false
// nodeQueue 队列添加二叉树的根节点
nodeQueue.push(root);
// pathQueue 队列添加二叉树的根节点的值
pathQueue.push(to_string(root->val));
// 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
while (!nodeQueue.empty())
{
// 从 nodeQueue 中取出一个节点，此时，nodeQueue 已经抛出了这个节点
TreeNode *node = nodeQueue.front();
nodeQueue.pop();
// 从 pathQueue 中取出一个元素，此时，nodeQueue 已经抛出了这个元素
string path = pathQueue.front();
pathQueue.pop();
// 判断当前节点的左子节点和右子节点是否存在
// 即判定当前节点是否是叶子节点，如果是叶子节点，那么就找到了一条路径
if (node->left == NULL && node->right == NULL)
{
// 把这条路径添加到结果数组中
res.push_back(path);
}
else
{
// 判断当前节点的左子节点是否存在，如果存在，顺着这个节点去寻找叶子节点
if (node->left != NULL)
{
// nodeQueue 队列添加这个存在的左子节点
nodeQueue.push(node->left);
// 接下来，需要把这个节点加入到 path 这条路径中
string strB = path;
// 添加 ->
strB = strB + "->";
// 添加当前节点的值
strB = strB + to_string(node->left->val);
// pathQueue 队列记录这条路径
pathQueue.push(strB);
}
if (node->right != NULL)
{
// nodeQueue 队列添加这个存在的左子节点
nodeQueue.push(node->right);
// 接下来，需要把这个节点加入到 path 这条路径中
string strB = path;
// 添加 ->
strB = strB + "->";
// 添加当前节点的值
strB = strB + to_string(node->right->val);
// pathQueue 队列记录这条路径
pathQueue.push(strB);
}
}
}
// 返回 res
return res;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二叉树的所有路径（ LeetCode 257 ）:https://leetcode-cn.com/problems/binary-tree-paths/submissions/
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
# res 存放所有从根节点到叶子节点的路径。
res = list()
# 边界情况处理
if not root :
return res
# 设置一个队列 nodeQueue，用来遍历存储二叉树中的元素
nodeQueue = deque()
# 设置一个队列 pathQueue，用来记录路径
pathQueue = deque()
# Queue 中 add() 和 offer()都是用来向队列添加一个元素
# 在容量已满的情况下，add() 方法会抛出 IllegalStateException 异常，offer() 方法只会返回 false
# nodeQueue 队列添加二叉树的根节点
nodeQueue.append(root)
# pathQueue 队列添加二叉树的根节点的值
pathQueue.append(str(root.val))
# 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
while nodeQueue :
# 从 nodeQueue 中取出一个节点，此时，nodeQueue 已经抛出了这个节点
node = nodeQueue.popleft()
# 从 pathQueue 中取出一个元素，此时，nodeQueue 已经抛出了这个元素
path = pathQueue.popleft()
# 判断当前节点的左子节点和右子节点是否存在
# 即判定当前节点是否是叶子节点，如果是叶子节点，那么就找到了一条路径
if not node.left and not node.right:
# 把这条路径添加到结果数组中
res.append(path)
else :
# 判断当前节点的左子节点是否存在，如果存在，顺着这个节点去寻找叶子节点
if node.left :
# nodeQueue 队列添加这个存在的左子节点
nodeQueue.append(node.left)
# 接下来，需要把这个节点加入到 path 这条路径中
# node.left 成功添加到 path 这条路径中，形成了 newPath
newPath = path + '->' + str(node.left.val)
# pathQueue 队列记录这条路径
pathQueue.append(newPath)
if node.right :
# nodeQueue 队列添加这个存在的左子节点
nodeQueue.append(node.right)
# 接下来，需要把这个节点加入到 path 这条路径中
# node.right 成功添加到 path 这条路径中，形成了 newPath
newPath = path + '->' + str(node.right.val)
# pathQueue 队列记录这条路径
pathQueue.append(newPath)
# 返回 res
return res
