剑指Offer 34.二叉树中和为某一值的路径:https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
思路:递归遍历并保存所有路径,然后计算符合要求的路径。
public List<List<Integer>> pathSum(TreeNode root, int target) { if (root == null) { return new ArrayList<>(); } List<List<Integer>> list = this.recursion(root); Iterator<List<Integer>> it = list.iterator(); while (it.hasNext()) { List<Integer> path = it.next(); int sum = path.stream().mapToInt(Integer::intValue).sum(); if (sum != target) { it.remove(); } else { Collections.reverse(path); } } return list; } public List<List<Integer>> recursion(TreeNode root) { List<List<Integer>> list = new ArrayList<>(); if (root.left == null && root.right == null) { List<Integer> path = new ArrayList<>(); list.add(path); } else { if (root.left != null) { list.addAll(this.recursion(root.left)); } if (root.right != null) { list.addAll(this.recursion(root.right)); } } for (List<Integer> path : list) { path.add(root.val); } return list; }
特定深度节点链表:https://leetcode-cn.com/problems/list-of-depth-lcci/
思路:递归遍历,使用map保存所有层的节点信息。然后转化为ListNode
public ListNode[] listOfDepth(TreeNode tree) { if (tree == null) { return new ListNode[0]; } Map<Integer, List<Integer>> map = new HashMap<>(); this.recursion(map, tree, 1); ListNode[] listNode = new ListNode[map.size()]; for (int i = 1; i <= map.size(); i++) { List<Integer> list = map.get(i); if (list == null) { break; } ListNode root = new ListNode(-1); ListNode curr = root; for (Integer node : list) { curr.next = new ListNode(node); curr = curr.next; } listNode[i - 1] = root.next; } return listNode; } public void recursion(Map<Integer, List<Integer>> map, TreeNode root, int depth) { List<Integer> list = map.get(depth); if (list == null) { list = new ArrayList<>(); map.put(depth, list); } list.add(root.val); depth++; if (root.left != null) { this.recursion(map, root.left, depth); } if (root.right != null) { this.recursion(map, root.right, depth); } }