LeetCode -- Binary Tree Paths
题目描述:
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1
/ \
2 3
\
5
All root-to-leaf paths are:
["1->2->5", "1->3"]
输入1个二叉树,打印出所有从根到叶子的路径。
思路:
1个基本的DFS题,直接从根对树做DFS,到叶子时收集路径即可。
实现代码:
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1
/ \
2 3
\
5
All root-to-leaf paths are:
["1->2->5", "1->3"]
输入1个二叉树,打印出所有从根到叶子的路径。
思路:
1个基本的DFS题,直接从根对树做DFS,到叶子时收集路径即可。
实现代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public IList<string> BinaryTreePaths(TreeNode root)
{
if(root == null){
return new List<string>();
}
var ret = new List<string>();
var p = "";
Dfs(root, ref ret, p);
return ret;
}
private void Dfs(TreeNode node, ref List<string> result, string path)
{
if(node == null){
return;
}
if(node.left == null && node.right == null)
{
Append(ref path, node.val);
result.Add(path);
return;
}
var nextPath = path;
Append(ref nextPath, node.val);
Dfs(node.left, ref result, nextPath);
Dfs(node.right, ref result, nextPath);
}
private void Append(ref string path,int val){
if(path == ""){
path = val.ToString();
return;
}
path = path + "->"+ val.ToString();
}
}