※【回溯】【深度优先前序】Leetcode 257. 二叉树的所有路径-Toy模板网

这篇具有很好参考价值的文章主要介绍了※【回溯】【深度优先前序】Leetcode 257. 二叉树的所有路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

---------------🎈🎈257. 二叉树的所有路径题目链接🎈🎈-------------------

※【回溯】【深度优先前序】Leetcode 257. 二叉树的所有路径,Leetcode,# 二叉树,深度优先,leetcode,算法,职场和发展,数据结构,java

解法0 迭代法

解法1 深度优先前序

时间复杂度O(N)
空间复杂度O(N)文章来源地址https://www.toymoban.com/news/detail-828340.html


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<String> result = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        helper(root,"");
        return result;
    }
    public void helper(TreeNode root, String s){
        // 前序 中左右
        
        if(root == null) return;
        if(root.left == null && root.right == null){
            result.add(s + root.val);
        }

        String temp = s + root.val + "->";
        helper(root.left,temp);
        helper(root.right,temp);
    }
}

解法2 深度优先前序添加了StringBulider

深度优先遍历添加了StringBulider替代字符串拼接提升效率
toString()转化为String
.append()添加元素

时间复杂度O(N)
空间复杂度O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<String> result = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        helper(root,"");
        return result;
    }
    public void helper(TreeNode root, String s){
        // 前序 中左右  使用StringBuilder提升效率
        
        // 停止条件
        if(root == null) return;
        if(root.left == null && root.right == null){ // 如果遍历到叶子节点，那么就在result中添加该路径（该路径就是前面得到的s+当前值）
            result.add(new StringBuilder(s).append(root.val).toString());
            return;
        }

        String temp = new StringBuilder(s).append(root.val).append("->").toString();  // 中 当前路径 s 加上当前节点值和箭头 "->" 的组合

        helper(root.left, temp);  // 左
        helper(root.right, temp); // 右
    }
}