力扣labuladong一刷day41天遍历思维强化共七题

力扣labuladong一刷day41天遍历思维强化

一、257. 二叉树的所有路径

题目链接：https://leetcode.cn/problems/binary-tree-paths/
思路：求所有路径和回溯非常像，回溯就可以求各种组合啦排序啦，一般回溯都是多叉树，这里二叉树求路径也是利用回溯，进入节点添加，离开节点删除。

/**
 * 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<>();
    List<Integer> list = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        traverse(root);
        return result;
    }
    void traverse(TreeNode root) {
        list.add(root.val);
        if (root.left == null && root.right == null) {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < list.size() - 1; i++) {
                builder.append(list.get(i)).append("->");
            }
            builder.append(list.get(list.size()-1));
            result.add(builder.toString());
        }
        if (root.left != null) {
            traverse(root.left);
            list.remove(list.size()-1);
        }
        if (root.right != null) {
            traverse(root.right);
            list.remove(list.size()-1);
        }
    }
}

二、129. 求根节点到叶节点数字之和

题目链接：https://leetcode.cn/problems/sum-root-to-leaf-numbers/
思路：

class Solution {
    List<Integer> list = new ArrayList<>();
    int sum = 0;
    public int sumNumbers(TreeNode root) {
        traverse(root);
        return sum;
    }

    void traverse(TreeNode root) {
        list.add(root.val);
        if (root.left == null && root.right == null) {
            int size = list.size();
            for (int i = 0; i < size; i++) {
                sum += (list.get(i) * Math.pow(10, size-i-1));
            }
        }
        if (root.left != null) {
            traverse(root.left);
            list.remove(list.size()-1);
        }
        if (root.right != null) {
            traverse(root.right);
            list.remove(list.size()-1);
        }
    }
}

三、199. 二叉树的右视图

题目链接：https://leetcode.cn/problems/binary-tree-right-side-view/
思路：方法一采用层序遍历，很直观很简单记录每一行最后一个元素。

class Solution {
     public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size-1) {
                    list.add(node.val);
                }
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return list;
    }
}

思路二，遍历计算深度，每第一次到达一个新深度时记录元素节点。前序遍历但要先遍历右子树，再遍历左子树。

class Solution {
    int max = -1;
    List<Integer> list = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        traverse(root, 0);
        return list;
    }
    
    void traverse(TreeNode root, int deep) {
        if (root == null) return;
        
        if (deep > max) {
            max = deep;
            list.add(root.val);
        }
        traverse(root.right, deep+1);
        traverse(root.left, deep+1);
    }
}

四、298. 二叉树最长连续序列

题目链接：https://leetcode.cn/problems/binary-tree-longest-consecutive-sequence/
思路：保留上一个节点值，利用回溯，每进入一个节点就进行比较，如果符合条件，len长度+1

class Solution {
     int max = 0;
    public int longestConsecutive(TreeNode root) {
        traverse(root, Integer.MAX_VALUE, 0);
        return max;
    }

    void traverse(TreeNode root, int pro, int len) {
        if (root == null) return;
        if (pro + 1 == root.val) {
            len++;
        }else {
            len = 1;
        }
        max = Math.max(max, len);
        traverse(root.left, root.val, len);
        traverse(root.right, root.val, len);
    }
}

五、988. 从叶结点开始的最小字符串

题目链接：https://leetcode.cn/problems/smallest-string-starting-from-leaf/
思路：也是遍历收集，利用回溯，到达叶子节点然后进行比较，只不过比较时可以直接使用string的compareTo方法来作为字典序的比较。

class Solution {
   String result;
    StringBuilder builder = new StringBuilder();
    public String smallestFromLeaf(TreeNode root) {
        traverse(root);
        return result;
    }

    void traverse(TreeNode root) {
        builder.append((char) ('a'+root.val));

        if (root.left == null && root.right == null) {
            String string = builder.reverse().toString();
            if (result == null || result.compareTo(string) > 0) {
                result = string;
            }
            builder.reverse();
            return;
        }

        if (root.left != null) {
            traverse(root.left);
            builder.deleteCharAt(builder.length()-1);
        }
        if (root.right != null) {
            traverse(root.right);
            builder.deleteCharAt(builder.length()-1);
        }
    }
}

六、1022. 从根到叶的二进制数之和

题目链接：https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers/
思路：和上一题类似还是回溯，到叶节点进行处理。

class Solution {
    List<Integer> list = new ArrayList<>();
    int sum = 0;
    public int sumRootToLeaf(TreeNode root) {
        traverse(root);
        return sum;
    }
    void traverse(TreeNode root) {
        list.add(root.val);
        if (root.left == null && root.right == null) {
            int len = list.size();
            for (int i = 0; i < len; i++) {
                sum += list.get(i) * Math.pow(2, len-i-1);
            }
            return;
        }
        if (root.left != null) {
            traverse(root.left);
            list.remove(list.size()-1);
        }
        if (root.right != null) {
            traverse(root.right);
            list.remove(list.size()-1);
        }
    }
}