LeetCode 257: Binary Tree Paths (DFS Backtracking with Path Builder)
LeetCode 257Binary TreeDFSToday we solve LeetCode 257 - Binary Tree Paths.
Source: https://leetcode.com/problems/binary-tree-paths/
English
Problem Summary
Given the root of a binary tree, return all root-to-leaf paths in any order. Each path should be represented as a string like "1->2->5".
Key Insight
This is a standard DFS traversal problem: maintain the current path while moving down the tree. Whenever we reach a leaf node, we join the path and append it to the answer list.
Brute Force and Limitations
A naive approach would copy full path strings at every recursion step, causing unnecessary allocations. A better approach keeps a mutable path container, pushes before recursion, and pops after recursion (backtracking).
Optimal Algorithm Steps
1) Handle empty tree: return empty list.
2) Start DFS from root with an empty list of node values.
3) At each node, append current value to path.
4) If leaf node, join path with "->" and add to result.
5) Otherwise recurse into left/right child.
6) Pop current value when returning (backtracking).
Complexity Analysis
Let n be number of nodes and h be tree height.
DFS visits each node once: traversal cost is O(n).
Building output strings costs total proportional to all path lengths, upper bounded by O(nh) in skewed cases.
Extra recursion/path space: O(h).
Common Pitfalls
- Forgetting to backtrack (missing pop).
- Treating nodes with one child as leaf nodes by mistake.
- Returning null instead of empty list for empty tree.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* 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) {
List<String> result = new ArrayList<>();
if (root == null) return result;
List<Integer> path = new ArrayList<>();
dfs(root, path, result);
return result;
}
private void dfs(TreeNode node, List<Integer> path, List<String> result) {
if (node == null) return;
path.add(node.val);
if (node.left == null && node.right == null) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < path.size(); i++) {
if (i > 0) sb.append("->");
sb.append(path.get(i));
}
result.add(sb.toString());
} else {
dfs(node.left, path, result);
dfs(node.right, path, result);
}
path.remove(path.size() - 1);
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func binaryTreePaths(root *TreeNode) []string {
res := []string{}
if root == nil {
return res
}
path := []int{}
var dfs func(*TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
path = append(path, node.Val)
if node.Left == nil && node.Right == nil {
parts := make([]string, len(path))
for i, v := range path {
parts[i] = strconv.Itoa(v)
}
res = append(res, strings.Join(parts, "->"))
} else {
dfs(node.Left)
dfs(node.Right)
}
path = path[:len(path)-1]
}
dfs(root)
return res
}/**
* 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) {
vector<string> result;
vector<int> path;
dfs(root, path, result);
return result;
}
private:
void dfs(TreeNode* node, vector<int>& path, vector<string>& result) {
if (!node) return;
path.push_back(node->val);
if (!node->left && !node->right) {
string s;
for (int i = 0; i < (int)path.size(); ++i) {
if (i) s += "->";
s += to_string(path[i]);
}
result.push_back(s);
} else {
dfs(node->left, path, result);
dfs(node->right, path, result);
}
path.pop_back();
}
};# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
res: List[str] = []
path: List[int] = []
def dfs(node: Optional[TreeNode]) -> None:
if not node:
return
path.append(node.val)
if not node.left and not node.right:
res.append("->".join(str(x) for x in path))
else:
dfs(node.left)
dfs(node.right)
path.pop()
dfs(root)
return res/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {string[]}
*/
var binaryTreePaths = function(root) {
const res = [];
const path = [];
const dfs = (node) => {
if (!node) return;
path.push(node.val);
if (!node.left && !node.right) {
res.push(path.join("->"));
} else {
dfs(node.left);
dfs(node.right);
}
path.pop();
};
dfs(root);
return res;
};中文
题目概述
给定二叉树根节点，返回所有从根节点到叶子节点的路径，路径格式为 "1->2->5" 这样的字符串。
核心思路
本题就是深度优先遍历。沿着递归向下时把当前节点值加入路径；到达叶子节点时把整条路径拼接成字符串加入答案；回溯时弹出节点值，恢复现场。
暴力解法与不足
如果每走一步都复制整条路径字符串，会带来大量重复分配。更稳妥做法是使用可变 path 容器：进入节点 push，离开节点 pop，通过回溯复用空间。
最优算法步骤
1）空树直接返回空数组。
2）从根节点启动 DFS，并维护当前路径数组。
3）访问节点时先加入路径。
4）若为叶子节点，则把路径按 "->" 拼接后加入结果。
5）否则继续递归左右子树。
6）递归返回前弹出当前节点（回溯）。
复杂度分析
设节点数为 n，树高为 h。
遍历节点开销为 O(n)；输出字符串总成本与所有路径长度总和相关，最坏可近似看作 O(nh)。
额外递归与路径空间为 O(h)。
常见陷阱
- 忘记回溯弹栈，导致路径污染。
- 把“只有一个孩子”的节点误判成叶子。
- 空树返回 null 而不是空数组。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* 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) {
List<String> result = new ArrayList<>();
if (root == null) return result;
List<Integer> path = new ArrayList<>();
dfs(root, path, result);
return result;
}
private void dfs(TreeNode node, List<Integer> path, List<String> result) {
if (node == null) return;
path.add(node.val);
if (node.left == null && node.right == null) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < path.size(); i++) {
if (i > 0) sb.append("->");
sb.append(path.get(i));
}
result.add(sb.toString());
} else {
dfs(node.left, path, result);
dfs(node.right, path, result);
}
path.remove(path.size() - 1);
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func binaryTreePaths(root *TreeNode) []string {
res := []string{}
if root == nil {
return res
}
path := []int{}
var dfs func(*TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
path = append(path, node.Val)
if node.Left == nil && node.Right == nil {
parts := make([]string, len(path))
for i, v := range path {
parts[i] = strconv.Itoa(v)
}
res = append(res, strings.Join(parts, "->"))
} else {
dfs(node.Left)
dfs(node.Right)
}
path = path[:len(path)-1]
}
dfs(root)
return res
}/**
* 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) {
vector<string> result;
vector<int> path;
dfs(root, path, result);
return result;
}
private:
void dfs(TreeNode* node, vector<int>& path, vector<string>& result) {
if (!node) return;
path.push_back(node->val);
if (!node->left && !node->right) {
string s;
for (int i = 0; i < (int)path.size(); ++i) {
if (i) s += "->";
s += to_string(path[i]);
}
result.push_back(s);
} else {
dfs(node->left, path, result);
dfs(node->right, path, result);
}
path.pop_back();
}
};# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
res: List[str] = []
path: List[int] = []
def dfs(node: Optional[TreeNode]) -> None:
if not node:
return
path.append(node.val)
if not node.left and not node.right:
res.append("->".join(str(x) for x in path))
else:
dfs(node.left)
dfs(node.right)
path.pop()
dfs(root)
return res/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {string[]}
*/
var binaryTreePaths = function(root) {
const res = [];
const path = [];
const dfs = (node) => {
if (!node) return;
path.push(node.val);
if (!node.left && !node.right) {
res.push(path.join("->"));
} else {
dfs(node.left);
dfs(node.right);
}
path.pop();
};
dfs(root);
return res;
};
Comments