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"]
``````

Tips:

Code：

recursion：

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
if (root == null) {
return result;
}
dfs(root, result, "");
return result;
}
private void dfs (TreeNode root, List<String> result, String s) {
if(root.left == null && root.right==null){
}
if(root.left != null) {
dfs(root.left, result, s+String.valueOf(root.val)+"->");
}
if(root.right !=null) {
dfs(root.right, result, s+String.valueOf(root.val)+"->");
}
}
}
``````

stack：

``````public class Solution {
public List<String> binaryTreePaths(TreeNode root) {

List<String> res = new ArrayList<String>();
Map<TreeNode, String> nodeMap = new HashMap<TreeNode, String>();

if (null == root) return res;

Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
nodeMap.put(root, String.valueOf(root.val));

while(!stack.isEmpty()) {
TreeNode node = stack.pop();

if ((null == node.left) && (null == node.right)) {
}
if (null != node.left) {
stack.push(node.left);
nodeMap.put(node.left, nodeMap.get(node)+"->" + String.valueOf(node.left.val));
}
if (null != node.right) {
stack.push(node.right);
nodeMap.put(node.right, nodeMap.get(node)+"->" + String.valueOf(node.right.val));
}
nodeMap.remove(node);

}
return res;
}
}
``````