傻逼时刻

二叉树所有路径

这个题目写了好久，越写越怀疑自己，一看是个简单等级的题目，更加怀疑自己写复杂了

不过最后两种方法都 ac 了，就是过程很坎坷；遍历三分钟，分解俩小时（略带夸张）

// 方案一：分解子问题思路（自己一开始惯性思维直接分解子问题）
// 可见代码之长，且还需要着重考虑叶子节点，不然就有问题
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) return new ArrayList<String>();
        List<List<Integer>> lists = binaryTreePathsHelper(root);
        List<String> res = new ArrayList<>();
        for (List<Integer> list : lists) {
            boolean first = true;
            StringBuffer sb = new StringBuffer();
            for (Integer num : list) {
                if (first) {
                    sb.append(num);
                    first = false;
                    continue;
                }
                sb.append("->").append(num);
            }
            res.add(sb.toString());
        }
        return res;
    }
    private List<List<Integer>> binaryTreePathsHelper(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        // if (root == null) {
        //     res.add(new ArrayList<Integer>());
        //     return res;
        // }
        // 如果为叶子节点
        if (root.left == null && root.right == null) {
            List<Integer> curList = new ArrayList<>();
            curList.add(root.val);
            res.add(curList);
        }
        // 如果不为叶子节点
        // 左孩子不为 null 才进行左递归
        // 右孩子不为 null 才进行右递归
        // 相当于排除了不对只有一个孩子节点的 root 进行返回，注意看上面注释掉的代码
        List<List<Integer>> leftRes = root.left != null ? binaryTreePathsHelper(root.left) : null;
        List<List<Integer>> rightRes = root.right != null ? binaryTreePathsHelper(root.right) : null;
        if (leftRes != null) {
            for (List<Integer> left : leftRes) {
                List<Integer> curList = new ArrayList<>();
                curList.add(root.val);
                curList.addAll(left);
                res.add(curList);
            }
        }
        if (rightRes != null) {
            for (List<Integer> right : rightRes) {
                List<Integer> curList = new ArrayList<>();
                curList.add(root.val);
                curList.addAll(right);
                res.add(curList);
            }
        }
        return res;
    }
}

// 方案二：遍历（发现新世界的大门）
// 借助全局变量（太舒服了）
class Solution {
    // 全局变量
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        traversal(root);
        List<String> res = new ArrayList<>();
        for (List<Integer> list : ans) {
            boolean first = true;
            StringBuffer sb = new StringBuffer();
            for (Integer num : list) {
                if (first) {
                    sb.append(num);
                    first = false;
                    continue;
                }
                sb.append("->").append(num);
            }
            res.add(sb.toString());
        }
        return res;
    }
    private void traversal(TreeNode root) {
        if (root == null) return ;
        // 先序遍历处理阶段：进入时就把当前节点加入 list 中
        list.add(root.val);
        // 注意：需要 new 新的 list 不然每次加入的都是指向同一地址的 list
        if (root.left == null && root.right == null) ans.add(new ArrayList<Integer>(list));
        // 递归阶段
        traversal(root.left);
        traversal(root.right);
        // 后序遍历处理阶段：离开时就把当前节点从 list 中去掉（当前节点在 list 中的最后一个位置上）
        list.remove(list.size() - 1);
    }
}

从根到叶的二进制数之和

小 tips

• 二进制 -> 十进制（位运算）

// 自己的傻逼方法：用数组存好每一种二进制顺序，然后二进制 -> 十进制求和
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public int sumRootToLeaf(TreeNode root) {
        traversal(root);
        int sum = 0;
        for (List<Integer> list : ans) {
            int s = 1;
            int t = 0;
            for (int i = list.size() - 1; i >= 0 ; i--) {
                t += s * list.get(i);
                s *= 2;
            }
            sum += t;
        }
        return sum;

    }
    private void traversal(TreeNode root) {
        if (root == null) return ;
        list.add(root.val);
        if (root.left == null && root.right == null) ans.add(new ArrayList<>(list));
        traversal(root.left);
        traversal(root.right);
        list.remove(list.size() - 1);
    }
}

// 高光时刻
class Solution {
    // 存储路径
    private int path = 0;
    // 存储总和
    private int sum = 0;
    public int sumRootToLeaf(TreeNode root) {
        traversal(root);
        return sum;
    }
    private void traversal(TreeNode root) {
        if (root == null) return ;
        // 进入：先序处理
        // 左移 1 位，然后和 root.val 或运算
        path = path << 1 | root.val;
        // 如果是叶子节点
        if (root.left == null && root.right == null) {
            sum += path;
            // 不能 return，不然不能执行到后面，导致 path 的值错误
            // return ;
        }
        traversal(root.left);
        traversal(root.right);
        // 离开：后序处理
        // 右移 1 位，清除 root.val 
        path = path >> 1;
    }
}