【Q257】(md) 二叉树的所有路径 给定一个二叉树，返回所有从根节点到 叶子节点 的路径。 说明: 叶子节点是指没有子节点的节点。 输出格式: [“1->2->5”, “1->3”]
class Solution { /* *【DFS深搜】 * DFS的思路朴实无华，但本题有两个值得思考的地方： * 1.需要判断某个节点是否为叶子节点 * 2.用String传参比StringBuilder传参更好，避免手动回溯的麻烦 */ public List<String> binaryTreePaths(TreeNode root) { DFS(root, ""); return res; } private List<String> res = new ArrayList<>(); private void DFS(TreeNode node, String s){ if(node != null){ StringBuilder sb = new StringBuilder(s); sb.append(node.val); if(node.left == null && node.right == null){ res.add(sb.toString()); }else{ sb.append("->"); DFS(node.left, sb.toString()); DFS(node.right, sb.toString()); } } } }
【Q60】(md) 第k个排列 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下： “123” “132” “213” “231” “312” “321” 给定 n 和 k，返回第 k 个排列。 示例 1: 输入: n = 3, k = 3 输出: “213” 示例 2: 输入: n = 4, k = 9 输出: “2314” 说明：给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。
class Solution { /* *【回溯】 */ public String getPermutation(int n, int k) { used = new boolean[n]; traceBack("", 0, n, k); return res; } private boolean[] used; private int count = 1; private String res; private void traceBack(String temp, int layer, int n, int k){ if(count > k){ return; } if(layer > n){ return; } if(layer == n){ if(count == k){ res = temp; } count++; return; } for(int i = 1; i <= n; i++){ if(!used[i - 1]){ used[i - 1] = true; traceBack(temp + i, layer + 1, n, k); used[i - 1] = false; } } } } // 可以使用数学方法对这种暴力的全排列进行优化
【Q102】(ez) 二叉树的层次遍历 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例： 二叉树：[3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7返回其层次遍历结果： [ [3], [9,20], [15,7] ]
class Solution { /** *【BFS】 * BFS可以倒背如流，但如何在BFS时候顺便根据深度分层呢？ * 在某一次出队前，记录此时队列的长度。不过之后又加了几个，这段长度即为一层。 */ public List<List<Integer>> levelOrder(TreeNode root) { if(root == null){ return new ArrayList<>(); } List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int count = queue.size(); List<Integer> list = new ArrayList<>(); while(count > 0){ TreeNode node = queue.poll(); list.add(node.val); if(node.left != null){ queue.add(node.left); } if(node.right != null){ queue.add(node.right); } count--; } res.add(list); } return res; } }
Qs from https://leetcode-cn.com ♠ loli suki ♥ end
