博文中会简要介绍Leetcode P0257题目分析及解题思路。
“Binary Tree Paths”是一道比较简单的题目，主要思路使用深度优先搜索来遍历整棵树，最后得到每个路径。
Given the root of a binary tree, return all root-to-leaf paths in any order.
A leaf is a node with no children.
以下是Java的题解代码实现。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
if (root == null)
return paths;
this.dfs(root, new StringBuilder());
return this.paths;
}
private List<String> paths = new ArrayList<>();
private void dfs(TreeNode cur, StringBuilder path) {
StringBuilder tmp = new StringBuilder(path);
tmp.append(cur.val);
// Reach the leaf node
if (cur.left == null && cur.right == null) {
paths.add(tmp.toString());
return;
}
tmp.append("->");
if (cur.left != null) {
this.dfs(cur.left, tmp);
}
if (cur.right != null) {
this.dfs(cur.right, tmp);
}
}
}
以下是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:
vector<string> binaryTreePaths(TreeNode* root) {
if (!root)
return paths;
_Dfs(root, "");
return paths;
}
private:
vector<string> paths;
void _Dfs(TreeNode *cur, string path) {
path += to_string(cur->val);
// Reach the leaf node
if (!cur->left && !cur->right) {
paths.push_back(path);
return;
}
path += "->";
if (cur->left)
_Dfs(cur->left, path);
if (cur->right)
_Dfs(cur->right, path);
}
};