左叶子之和、二叉树的所有路径。

忽闻暴风大作~~~~~

                        断崖边一老者慢慢睁开苍老的眼睛，嘴里喃喃道：

算法江湖又要腥风血雨了。。。。。。。。。。。。

        算法凡界公元2022年，一年一度的算法大宗：“暴力宗”又开始了他们的盛大筛选活动，暴力宗在江湖上声望极高，其宗主：暴力哥更是leetcode算法榜前十的算法强者！

---

欢迎各位来宾、各位参选者的到来，本人代表暴力宗欢迎各位，若有招待不周，还请见谅。转眼间，又到了一年一度的暴力宗外院选拔弟子的日子，本次选拔，只有两题作为题目，完成时间更快、时间复杂度更低的人员可进入外院修行！

        一炷香后，只见原本嘈杂的广场，已经变得井然有序，只见金光一闪，每个参选的隔间中出现了两道题目：

1：

        给定二叉树，计算左叶子节点的和。

        404. 左叶子之和 - 力扣（LeetCode）

2：

        给定二叉树，输出全部路径。

        力扣 (leetcode.cn)

时间一分一秒的过去，维度1024号考生只字未动，各大监考官都感到诧异，难道这位考生不在乎入围暴力宗的名额？

事情并非如此，只见这位考生在最后半炷香的时刻，突然睁眼：挥笔如下：

首先，我们直接使用最简单的前序递归遍历解决第一个题 ：

直接遍历全部节点，在递归时，传入一个标识符，1为左节点，2为右节点，开始传入0.

在遍历过程中要注意，不要直接进行左右节点的递归，因为在判断结束条件是，并不是当前节点为空就退出，而是判断左右节点为空并且标识符为1时（这时就说明，已经到达了叶子节点）。

上笔记：

/**
 * 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  int sumOfLeftLeaves(TreeNode root) {
        dfs(root, 0);
        return ans;
    }
 
     int ans = 0;
 
    private  void dfs(TreeNode root, int k) {
        if (root.left == null && root.right == null) {
            if (k == 1) {
                ans += root.val;
            }
            return;
        }
        if (root.left != null) {
            dfs(root.left, 1);
        }
        if (root.right != null) {
            dfs(root.right, 2);
        }
    }
}

 监考官无一不惊呼！此技甚妙啊！！

当看见第二道题时，监考官都已经惊呆了！

只见该男子深吸一口气，再次拿起黑笔写下题解：

1：

        既让要给出路径，那么就要遍历全部路径，肯定也需要使用回溯。

/**
 * 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 binaryTreePaths(TreeNode root) {
        dfs(root);
        return list;
    }
 
     List list = new ArrayList<>();
     String str = "";
 
    private  void dfs(TreeNode root) {
        String t = str;
        if (root.left == null && root.right == null) {
            str += root.val;
           // System.out.println(str);
            list.add(str);
            str = t;
            return;
        }
        str += root.val + "->";
        //System.out.println(root.val);
         if (root.left != null) {
            dfs(root.left);
        }
        if (root.right != null) {
            dfs(root.right);
        }
        str = t;
    }
}

 这里要注意的是，存入时不要将存入放在递归循环中，处理最后一次会非常麻烦。这里还有可以优化的地点：

将String改成StringBuilder，在存入集合时，再改回来，时间复杂度和空间复杂度将会提高许多，留给大家去实现吧~

 提笔收笔行如流水！丝毫不带停顿。该男子写完题解正准备踱步而走，第一监考官马上拦到他面前，恭恭敬敬的行了礼，说到：真是长江后浪推前浪啊，少年如此本事，在外院屈才了，我正式邀请你前往内院修行，如何？

只见男子嘴角一笑，不屑说到：我只是来试一下贵宗的本领，没想到如此简单，想必贵总也没什么本领吧！

第二监考官挺严，极力呵斥到：放肆！我暴力宗岂是你能评价的！我这里还有一道千古难题，只有本宗宗主解开过，你要是能解开，莫说内院，我这个长老直接给你来做！

好！该少年一口应下,带路，拿题来！

                                                                                                                未完待续。。。。。。