为什么80%的码农都做不了架构师？>>> 
问题：
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"]
解决：
① 简单的二叉树遍历，遍历的过程中记录之前的路径，一旦遍历到叶子节点便将该路径加入结果中。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution { //17ms
List<String> res = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
if(root != null) findPath(root,String.valueOf(root.val));
return res;
}
public void findPath(TreeNode node,String path){
if(node.left == null && node.right == null) res.add(path);
if(node.left != null) findPath(node.left,path + "->" + node.left.val);
if(node.right != null) findPath(node.right,path + "->" + node.right.val);
}
}
② 进化版
public class Solution { //15ms
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<String>();
if (root == null) return res;
getPath(root, "", res);
return res;
}
public void getPath(TreeNode root, String path, List<String> res) {
if (root.left == null && root.right == null)
res.add(path + root.val);
else {
if (root.left != null) getPath(root.left, path + root.val + "->", res);
if (root.right != null) getPath(root.right, path + root.val + "->", res);
}
}
}
【注意】return影响效率
public class Solution { //15ms
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<String>();
if (root == null) return res;
getPath(root, "", res);
return res;
}
public void getPath(TreeNode root, String path, List<String> res) {
if (root.left == null && root.right == null){
res.add(path + root.val);
//return; 加上return耗时为18ms
}
if (root.left != null) getPath(root.left, path + root.val + "->", res);
if (root.right != null) getPath(root.right, path + root.val + "->", res);
}
}
