给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
分析:这道题看到所有路径时,该明白这是要用到回溯方法,而看到根节点到叶子结点时,同样明白,此题是要用到前序遍历来做。根据回溯的方法,为了递归时的方便,在方法外定义ret和path变量,之后以前序遍历的方式开始书写。递归的sup方法不用返回值。
public List
sup(root);
return ret;
}
List
List
private void sup(TreeNode node){
path.add(node.val);
if(node.left==null&&node.right==null){
StringBuilder sb = new StringBuilder();
for(int i=0;i
sb.append(“->”);
}
sb.append(path.get(path.size()-1));
ret.add(sb.toString());
return;
}
if(node.left!=null){
sup(node.left);
path.remove(path.size()-1); //回溯
}
if(node.right!=null){
sup(node.right);
path.remove(path.size()-1); //回溯
}
}
