思路:
最直观的方法是使用深度优先搜索,需要考虑当前的节点以及它的孩子节点。
- 如果当前节点不是叶子节点,则在当前的路径末尾添加该节点,并继续递归遍历该节点的每一个孩子节点。
- 如果当前节点是叶子节点,则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径,将该路径加入到List答案即可。
自顶向下,前序遍历
无常见的终止条件,而是用if(root!=null)
来控制递归
递归时要传入前面所记录的路径,除了最后的叶子节点外,前面记录的路径可能被多个节点重复使用到,所以在递归时要传入path
Java实现:
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths=new ArrayList<>();
check(root,"",paths);
return paths;
}
void check (TreeNode root, String path, List<String> paths){
//特殊,没有终止条件,由 if条件限制递归
if(root!=null){
StringBuffer pathTem=new StringBuffer(path); // 记录路径
pathTem.append(String.valueOf(root.val)); // 不管是不是叶子节点,直接记录当前节点至路径
if(root.left==null && root.right==null){ // 当前root是叶子节点
paths.add(pathTem.toString()); // 加入当前整个路径到List中
}else{ // 当前不是叶子节点,继续递归
pathTem.append("->");
// 要传入上一层记录的路径pathTem.toStirng
check(root.left,pathTem.toString(),paths);
check(root.right,pathTem.toString(),paths);
}
}
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/89315.html