【算法千题案例】⚡️每日LeetCode打卡⚡️——64. 二叉树的所有路径

---

📢前言

🚀 算法题 🚀

• 🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
• 🌲 提示：本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
• 🌲 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧🧐！
• 🌲 今天是力扣算法题持续打卡第64天🎈！

🚀 算法题 🚀

---

🌲原题样例：二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例1:

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例2:

输入：root = [1]
输出：["1"]

提示：

• 树中节点的数目在范围 [1, 100] 内
• 100 <= Node.val <= 100

---

🌻C#方法：递归

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
public IList<string> BinaryTreePaths(TreeNode root)
    {
        List<string> res = new List<string>();
        Backtrack257(root, root.val.ToString(), res);
        return res;
    }
    private void Backtrack257(TreeNode root, string path, List<string> res)
    {
        if (root.left == null && root.right == null)
        {
            res.Add(path);
            return;
        }
        if (root.left != null)
            Backtrack257(root.left, path + "->" + root.left.val.ToString(), res);
        if (root.right != null)
            Backtrack257(root.right, path + "->" + root.right.val.ToString(), res);
    }
}

执行结果

通过
执行用时：156 ms，在所有 Java  提交中击败了83.33%的用户
内存消耗：41 MB，在所有 Java 提交中击败了20.37%的用户

---

🌻Java 方法：深度优先搜索

思路解析

最直观的方法是使用深度优先搜索。在深度优先搜索遍历二叉树时，我们需要考虑当前的节点以及它的孩子节点。

• 如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。
• 如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径，将该路径加入到答案即可。

如此，当遍历完整棵二叉树以后我们就得到了所有从根节点到叶子节点的路径。当然，深度优先搜索也可以使用非递归的方式实现，这里不再赘述。

代码：

/**
 * 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 {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<String>();
        constructPaths(root, "", paths);
        return paths;
    }

    public void constructPaths(TreeNode root, String path, List<String> paths) {
        if (root != null) {
            StringBuffer pathSB = new StringBuffer(path);
            pathSB.append(Integer.toString(root.val));
            if (root.left == null && root.right == null) {  // 当前节点是叶子节点
                paths.add(pathSB.toString());  // 把路径加入到答案中
            } else {
                pathSB.append("->");  // 当前节点不是叶子节点，继续递归遍历
                constructPaths(root.left, pathSB.toString(), paths);
                constructPaths(root.right, pathSB.toString(), paths);
            }
        }
    }
}

执行结果

通过
执行用时：1 ms，在所有 Java  提交中击败了100.00%的用户
内存消耗：38.5 MB，在所有 Java 提交中击败了73.86%的用户

复杂度分析

时间复杂度：O( n^2 )
空间复杂度：O( n^2 ) ，其中 Σ 是字符串的字符集。哈希表存储字符的空间取决于字符串的字符集大小，最坏情况下每个字符均不相同，需要O(∣Σ∣) 的空间。

---

💬总结

• 今天是力扣算法题打卡的第六十四天！
• 文章采用 C#和 Java 两种编程语言进行解题
• 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
• 那今天的算法题分享到此结束啦，明天再见！