算法 | 第4章树与图相关《程序员面试金典》#yyds干货盘点# _第4章

登山则情满于山，观海则意溢于海。这篇文章主要讲述算法 | 第4章树与图相关《程序员面试金典》#yyds干货盘点#相关的知识，希望能为你提供帮助。
@[TOC](第4章树与图相关《程序员面试金典》)
前言本系列笔记主要记录笔者刷《程序员面试金典》算法的一些想法与经验总结，按专题分类，主要由两部分构成：经验值点和经典题目。其中重点放在经典题目上；
本章有10题，标号到12，没有第7和第11题；
0. *经验总结 0.1 程序员面试金典 P85

树的基本组成单位是节点node，节点可以封装左右指针、父节点指针等；
可以使用一个名为Tree的类来封装节点，但在面试中不常用；如果使用Tree类能使代码简单或完善，可以使用Tree类；
注意区分以下概念，以及一些树的基本特点与遍历特点《详情见第0.2点各种树的特点》：
- 树与二叉树；
- 二叉树和二叉搜索树（又称二叉排序树）；
- 平衡与不平衡；
- 完整二叉树；
- 满二叉树；
- 完美二叉树；
- 二叉堆（小顶堆和大顶堆）
- 单次查找树（前序树）
- 顺序存储二叉树；
- 线索化二叉树；
- 霍夫曼树；
- B树、B+树和B*树；

0.2 各种树的特点 1. 二叉搜索树（二叉排序树）

文章图片

全部左边子孙节点 < = n < = 全部右边子孙节点；
碰到二叉树时，很多面试者会假定面试官问的是二叉搜索树，此时要务必问清是否的二叉搜索树；

2. 平衡二叉树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树；
树是否平衡需要跟面试官确认；
思考方向可以有：“平衡”树实际上多半意味着“不是非常不平衡的树”。其平衡性足以保证执行insert和find操作可以在O(log n)的时间复杂度内完成，但不一定是严格意义上的平衡树；
平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等；

3. 完整二叉树

文章图片

除最后一层，其它层被填满，并且最后一层节点从左到右填充；
中序遍历结果按顺序排列；

4. 满二叉树

文章图片

每个节点都有0个或两个子节点，不存在只有一个子节点的节点；

5. 完满二叉树

文章图片

完满二叉树既是完整二叉树，又是满二叉树；
正好有2^k^-1个节点；

6. 二叉堆（小顶堆和大顶堆）

文章图片

一个二叉堆是一个完整二叉树，每个节点值小于其左右子节点；
向最小堆插入元素，总是从最底部、最右边节点开始，通过与其祖先节点交换来向上传递较小值；
删除最小堆最小元素，将堆中最后一个元素放在顶节点，通过与子节点交换来向下传递较大值；
上述两个算法时间复杂度为O(log n)；

7. 单次查找树（前序树）

文章图片

*节点（有时称空节点）代表一个完整单次；
相比散列表可以识别字符串是否是任何有效单次的前缀，可以在O(K)的时间复杂度内检查字符串是否为有效前缀；
涉及一组有效单词的问题可以使用单次查找树进行优化；

8. 顺序存储二叉树

文章图片

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组；
顺序二叉树通常只考虑完全二叉树；
第n个元素的左子节点为2*n+1；
第n个元素的右子节点为2*n+2；
第n个元素的父节点为 (n-1)/2；
n : 表示二叉树中的第几个元素(按0开始编号如图所示)；

9. 线索化二叉树

文章图片

n个结点的二叉链表中含有 2n-(n-1)=n+1 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为" 线索" ）；

10. 霍夫曼树

文章图片

给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)；

11. B树、B+树和B*树

文章图片

文章图片

0.3 树的三种遍历方式中序遍历：

void inOrderTraversal(TreeNode node) if(node != null) inOrderTraversal(node.left); visit(node); inOrderTraversal(node.right);

前序遍历：

void preOrderTraversal(TreeNode node) if(node != null) visit(node); preOrderTraversal(node.left); preOrderTraversal(node.right);

后序遍历：

void postOrderTraversal(TreeNode node) if(node != null) postOrderTraversal(node.left); postOrderTraversal(node.right); visit(node);

0.4 图的表示形式与搜索图的表示方式：

邻接链表法；
邻接矩阵法；
邻接矩阵法使用BFS搜索，效率会比较低，因为需要迭代所有结点以便找到相邻节点；

图的搜索：

深度优先搜索（DFS）;
- 访问图中所有节点，或者访问最少节点直至找到某节点，DFS一般比较简单；
广度优先搜索（BFS）；
- 如果想找到两个节点的最短路径（或任意路径），BFS一般比较适宜；
- BFS是通过队列实现；
双向搜索；
- 双向搜索用于查找起始节点和目的节点间的最短路径；
- 本质上是从起始节点和目的节点同时开始的两个广度优先搜索；
- 当两个搜索相遇时，即找到一条路径

文章图片

文章图片

深度优先搜索（DFS）：

前序和树遍历的其他形式都是一种DFS；

void search(Node root) if(root == null) return; visit(root); root.visited = true; for each(Node n in root.adjacent) if(n.visited == false) search(n);

广度优先搜索（BFS）：

void search(Node root) Queue queue = new Queue(); root.marked = true; queue.enqueue(root); //加入队尾while(!queue.isEmpty()) Node r = queue.dequeue(); //从队列头部删除 visit(r); for each(Node n in r.adjacent) if(n.mark == false) n.marked = true; queue.enqueue(n);

1. 节点间通路 [medium]

文章图片

1.1 考虑点

询问面试官重复的边是否是双向边，本题中不是。笔者以为是双向边，第五种解法给出思路；
可以跟面试官讨论广度优先搜索和深度优先搜索的利弊：
- 广度优先搜索：适合查找最短路径；
- 深度优先搜索：实现比较简单，递归即可；在访问邻近节点之前，可能会深度遍历其中一个邻近节点；

1.2 解法 1.2.1 广度优先遍历法（优）

public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) Queue< Integer> queue = new LinkedList< > (); boolean[] isVisit = new boolean[n]; isVisit[start] = true; queue.offer(start); while( !queue.isEmpty() ) int thisNode = queue.poll(); int toNode; for(int i = 0; i < graph.length; i++) if(graph[i][0] == thisNode) toNode = graph[i][1]; if(toNode == target) return true; if(!isVisit[toNode]) isVisit[toNode] = true; queue.offer(toNode); return false;

执行时间：91.21%；内存消耗：92.42%；
适用于n较少的时候，当n过大会超时；

1.2.2 深度优先遍历法

private boolean[] visited = null; public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) this.visited = new boolean[graph.length]; return helper(graph, start, target); private boolean helper(int[][] graph, int start, int target) for (int i = 0; i < graph.length; ++i) // 确保当前路径未被访问（该判断主要是为了防止图中自环出现死循环的情况） if (!visited[i]) // 若当前路径起点与终点相符，则直接返回结果 if (graph[i][0] == start & & graph[i][1] == target) return true; // 设置访问标志 visited[i] = true; // DFS关键代码，思路：同时逐渐压缩搜索区间 if (graph[i][1] == target & & helper(graph, start, graph[i][0])) return true; // 清除访问标志 visited[i] = false; return false;

执行时间：81.17%；内存消耗：97.41%；
首先设置访问状态数组
使用DFS「深度优先搜索」进行递归搜索，逐渐压缩搜索区间，直至最终找到start与target在同一个路径内，则说明查找成功；

1.2.3 邻接矩阵的幂的性质

public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) int[][] adjacentMatrix = new int[n][n]; for (int[] edge : graph) adjacentMatrix[edge[0]][edge[1]] = 1; for (int i = 1; i < = n; i++) int[][] matrix = matrixPow(adjacentMatrix, i); if (matrix[start][target] != 0) return true; return false; public int[][] matrixPow(int[][] matrix, int n) int size = matrix.length; int[][] res = new int[size][]; for (int i = 0; i < size; i++) res[i] = Arrays.copyOf(matrix[i], size); for (int i = 1; i < n; i++) for (int row = 0; row < size; row++) int[] tmp = new int[size]; for (int col = 0; col < size; col++) for (int j = 0; j < size; j++) tmp[col] += res[row][j] * matrix[j][col]; res[row] = Arrays.copyOf(tmp, size); return res;

在本测试用例中超时；
用到邻接矩阵的幂的性质；

1.2.4 当重复边为双向边时

public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) int[] count = new int[n*(n-1)/2]; for(int i = 0; i < graph.length; i++) int mark = (2*n-1-graph[i][0])*graph[i][0]/2-1+graph[i][1]-graph[i][0]; count[mark]++; if(count[mark] == 2) int cache = graph[i][0]; graph[i][0] = graph[i][1]; graph[i][1] = cache; Queue< Integer> queue = new LinkedList< > (); boolean[] isVisit = new boolean[n*(n-1)/2]; queue.offer(start); while( !queue.isEmpty() ) int thisNode = queue.poll(); int toNode; for(int i = 0; i < graph.length; i++) int mark = (2*n-1-graph[i][0])*graph[i][0]/2-1+graph[i][1]-graph[i][0]; if(graph[i][0] == thisNode & & !isVisit[mark]) toNode = graph[i][1]; if(toNode == target) return true; queue.offer(toNode); return false;

相比前面做法增加了个方向倒转，也就是把重复边的方向倒转；

2. 最小高度树 [easy]

文章图片

2.1 考虑点

要创建最小生成树，就必须让左右子树的节点数量尽可能接近；

2.2 解法 2.2.1 递归法（优）

public TreeNode sortedArrayToBST(int[] nums) if(nums.length == 0) return null; int l = 0; int r = nums.length-1; return recur(l, r, nums); public TreeNode recur(int l, int r, int[] nums) if(l > r) return null; int mid = (l+r)/2; int headVal = nums[mid]; TreeNode head = new TreeNode(headVal); head.left= recur(l, mid-1, nums); head.right = recur(mid+1, r, nums); return head;

执行时间：100.00%；内存消耗：53.37%；
时间复杂度：O(n)。数组中的元素都使用1次，时间复杂度为O(n)；
空间复杂度：O(log n )。递归使用栈辅助空间，空间复杂度O(log n )；
注意递归结束条件，没有等于是因为递归里有对mid增减进行操作；
注意递归的参数l和r，表示需要递归的范围，不包括mid头结点；

2.2.2 BFS广度优先遍历

public TreeNode sortedArrayToBST(int[] num) if (num.length == 0) return null; Queue< int[]> rangeQueue = new LinkedList< > (); Queue< TreeNode> nodeQueue = new LinkedList< > (); int lo = 0; int hi = num.length - 1; int mid = (lo + hi) > > 1; TreeNode node = new TreeNode(num[mid]); rangeQueue.add(new int[]lo, mid - 1); rangeQueue.add(new int[]mid + 1, hi); nodeQueue.add(node); nodeQueue.add(node); while (!rangeQueue.isEmpty()) int[] range = rangeQueue.poll(); TreeNode currentNode = nodeQueue.poll(); lo = range[0]; hi = range[1]; if (lo > hi) continue; mid = (lo + hi) > > 1; int midValue = https://www.songbingjia.com/android/num[mid]; TreeNode newNode = new TreeNode(midValue); if (midValue > currentNode.val) currentNode.right = newNode; else currentNode.left = newNode; if (lo < hi) rangeQueue.add(new int[]lo, mid - 1); rangeQueue.add(new int[]mid + 1, hi); nodeQueue.add(newNode); nodeQueue.add(newNode); return node;

执行时间：100.00%；内存消耗：5.01%；
把数组不停的分为两部分，保存在队列中，然后不停的出队，创建结点；

3. 特定深度节点链表 [medium]

文章图片

3.1 考虑点

不需要逐一遍历每一层，可以用任意方式遍历整棵树，只需要记住节点位于哪一层即可；

3.2 解法 3.2.1 使用栈暴力法

public ListNode[] listOfDepth(TreeNode tree) if(tree == null) return null; Queue< TreeNode> queue = new LinkedList< > (); queue.offer(tree); int floor = 1; //第x-1层节点个数 List< ListNode> listArr = new ArrayList< > (); //当队列不为空 while(!queue.isEmpty()) //按层处理 int count = 0; //count用来储存第x层节点个数 ListNode head = null; ListNode cur = null; for(int i = 0; i < floor; i++) TreeNode node = queue.poll(); //创建链表 if(i == 0) head = new ListNode(node.val); cur = head; else ListNode nodeL = new ListNode(node.val); cur.next = nodeL; cur = nodeL; //加入队列 if( node.left != null) count++; queue.offer(node.left); if(node.right != null) count++; queue.offer(node.right); listArr.add(head); floor = count; //替换floorListNode[] list = new ListNode[listArr.size()]; for(int i = 0; i < listArr.size(); i++) list[i] = listArr.get(i); return list;

执行时间：89.59%；内存消耗：75.08%；
需要注意几个细节：
- ListNode cur = null：需要对cur初始化；
- floor = count：记得要替换floor；
由于事先不知道数组个数，先用一个ArrayList装起来，然后再转换成数组；

3.2.2 使用栈暴力法（代码优化缩短）

public ListNode[] listOfDepth(TreeNode tree) if(tree == null) return null; Queue< TreeNode> queue = new LinkedList< > (); queue.offer(tree); List< ListNode> listArr = new ArrayList< > (); //当队列不为空 while(!queue.isEmpty()) //按层处理 int size = queue.size(); ListNode head = new ListNode(0); ListNode cur = head; for(int i = 0; i < size; i++) TreeNode node = queue.poll(); //创建链表 cur.next = new ListNode(node.val); //加入队列 if( node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); cur = cur.next; listArr.add(head.next); return listArr.toArray(new ListNode[] );

执行时间：89.59%；内存消耗：25.97%；
思路同上，更多调用java的api简化代码；

3.2.3 递归法（优）

public ListNode[] listOfDepth(TreeNode tree) List< ListNode> list = new ArrayList< > (); dfs(list, tree, 1); ListNode[] arr = new ListNode[list.size()]; for (int i = 0; i < arr.length; i++) arr[i] = list.get(i); return arr; private void dfs(List< ListNode> list, TreeNode node, int deep) if (node == null) return; if (deep > list.size()) list.add(new ListNode(node.val)); else ListNode n = list.get(deep - 1); while (n.next != null) n = n.next; n.next = new ListNode(node.val); dfs(list, node.left, deep + 1); dfs(list, node.right, deep + 1);

执行时间：100.00%；内存消耗：96.63%；
定义树深度为deep，同一个深度的保存到同一个ListNode；

4. 检查平衡性 [easy]

文章图片

4.1 考虑点

其实，只需要一个checkHeight函数即可，它既可以计算高度，也可以平衡检查。可以使用整数返回值表示两者；

4.2 解法 4.2.1 自顶向下的递归

public boolean isBalanced(TreeNode root) if(root == null) return true; int deep = 1; int rootLeftDeep = findDeep(root.left, deep); int rootRightDeep = findDeep(root.right, deep); if(rootLeftDeep == -1 || rootRightDeep == -1) return false; int result = Math.abs(rootLeftDeep - rootRightDeep); return result< 2; public int findDeep(TreeNode node, int deep) if(node == null) return deep-1; if(node.left == null & & node.right == null) return deep; deep++; int leftDeep = findDeep(node.left,deep); int rightDeep = findDeep(node.right,deep); int deepDiff = Math.abs(leftDeep-rightDeep); return deepDiff> 1 ? -1 : Math.max(leftDeep,rightDeep);

执行时间：88.57%；内存消耗：20.48%；
方法虽然可行，但不高效，Math.abs()方法会被反复调用计算同一个节点的高度；

4.2.2 自顶向下的递归

public boolean isBalanced(TreeNode root) if (root == null) return true; else return Math.abs(height(root.left) - height(root.right)) < = 1 & & isBalanced(root.left) & & isBalanced(root.right); public int height(TreeNode root) if (root == null) return 0; else return Math.max(height(root.left), height(root.right)) + 1;

执行时间：88.57%；内存消耗：74.16%；
时间复杂度：O(n^2^)，其中 n 是二叉树中的节点个数。最坏情况下，二叉树是满二叉树，需要遍历二叉树中的所有节点，时间复杂度是 O(n)。对于节点 p，如果它的高度是 d，则 height(p) 最多会被调用 d 次（即遍历到它的每一个祖先节点时）。对于平均的情况，一棵树的高度 h 满足 O(h)=O(logn)，因为 d≤h，所以总时间复杂度为 O(nlogn)。对于最坏的情况，二叉树形成链式结构，高度为 O(n)，此时总时间复杂度为 O(n^2^)；
空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n；

4.2.3 自底向上的递归（优）

public boolean isBalanced(TreeNode root) return height(root) > = 0; public int height(TreeNode root) if (root == null) return 0; int leftHeight = height(root.left); int rightHeight = height(root.right); if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) return -1; else return Math.max(leftHeight, rightHeight) + 1;

执行时间：88.57%；内存消耗：96.72%；
时间复杂度：O(n)，其中 n 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)；
空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n；

5. 合法二叉搜索树 [medium]

文章图片

5.1 考虑点

有两种思路：
- 一是利用中序遍历；
- 二是建立在 left < current< right 这项特性上；

5.2 解法 5.2.1 递归法

class Solution Stack< Integer> stack = new Stack< > (); boolean isFlag = false; public boolean isValidBST(TreeNode root) if(root == null) return true; inOrderTraversal(root); return !isFlag; public void inOrderTraversal(TreeNode node) if(isFlag) return; if(node == null) return; inOrderTraversal(node.left); if(stack.isEmpty()) stack.push(node.val); else if(stack.peek() > = node.val) isFlag = true; return; else stack.push(node.val); inOrderTraversal(node.right);

执行时间：32.30%；内存消耗：91.41%；

5.2.2 中序遍历非递归

public boolean isValidBST(TreeNode root) Deque< TreeNode> stack = new LinkedList< TreeNode> (); double inorder = -Double.MAX_VALUE; while (!stack.isEmpty() || root != null) while (root != null) stack.push(root); root = root.left; root = stack.pop(); // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树 if (root.val < = inorder) return false; inorder = root.val; root = root.right; return true;

执行时间：24.37%；内存消耗：98.61%；
时间复杂度 : O(n)，其中 n 为二叉树的节点个数。二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)；
空间复杂度 : O(n)，其中 n 为二叉树的节点个数。栈最多存储 n 个节点，因此需要额外的 O(n) 的空间；

5.2.3 中序遍历递归（优）

//前一个结点，全局的 TreeNode prev; public boolean isValidBST(TreeNode root) if (root == null) return true; //访问左子树 if (!isValidBST(root.left)) return false; //访问当前节点：如果当前节点小于等于中序遍历的前一个节点直接返回false。 if (prev != null & & prev.val > = root.val) return false; prev = root; //访问右子树 if (!isValidBST(root.right)) return false; return true;

执行时间：100.00%；内存消耗：65.74%；
中序遍历时，判断当前节点是否大于中序遍历的前一个节点，也就是判断是否有序，如果不大于直接返回 false

6. 后继者 [medium]

文章图片

6.1 考虑点

因为是二叉搜索树，可以很方便找到节点，再根据是否有右子树分类判断；

6.2 解法 6.2.1 中序遍历递归法

class Solution Stack< TreeNode> stack = new Stack< > (); TreeNode findNode = null; public TreeNode inorderSuccessor(TreeNode root, TreeNode p) if(root == null || p == null) return null; inOrderTravarsal(root,p); return findNode!=null ? findNode : null; public void inOrderTravarsal(TreeNode node, TreeNode p) if(findNode != null) return; if(node == null) return; inOrderTravarsal(node.left, p); if(stack.isEmpty()) stack.push(node); else if(p.equals(stack.peek())) findNode = node; stack.pop(); //忘记pop return; else stack.push(node); inOrderTravarsal(node.right, p);

执行时间：72.07%；内存消耗：9.51%；

6.2.2 中序遍历非递归法（优）

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) TreeNode pre = null; while(root.val!=p.val) //右边 if(p.val > root.val) root = root.right; //左边 else pre = root; root = root.left; //假如没有右子树 if(root.right==null) return pre; else root = root.right; while(root.left!=null) root = root.left; return root;

执行时间：100.00%；内存消耗：100.00%；
找到节点后，如果右子树存在，那就是右子树最左边的节点。如果右子树不存在，表示已经访问n层子树，需要回到n的父节点q；如果n在q的左边，那就是q。反之需要往上访问，直到找到还未完全遍历的节点x；

8. 首个共同祖先 [medium]

文章图片

8.1 考虑点

如果是二叉搜索树，可以看看两条路径在哪开始分叉；

8.2 解法 8.2.1 深度优先遍历

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) if(root == null) return null; else if(root.equals(p)) return p; else if(root.equals(q)) return q; TreeNode leftNode = lowestCommonAncestor(root.left,p,q); TreeNode rightNode = lowestCommonAncestor(root.right,p,q); if(leftNode == null & & rightNode == null) return null; if(leftNode != null & & rightNode == null) if(leftNode.equals(q)) return q; else if(leftNode.equals(p)) return p; else return leftNode; if(leftNode == null & & rightNode != null) if(rightNode.equals(q)) return q; else if(rightNode.equals(p)) return p; else return rightNode; //注意非空校验 if((leftNode.equals(p) & & rightNode.equals(q)) || (leftNode.equals(q) & & rightNode.equals(p))) return root; return null;

执行时间：52.31%；内存消耗：5.19%；

8.2.2 深度优先遍历的简便写法（优）

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) // 到底了还没找到，返回 null if (root == null) return null; // 如果找到了 p 或 q，返回它 if (root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); // 如果 left 和 right 都记录了找到的节点，那么肯定是一个记录了 p ，另一个记录了 q // 它们分别在以 root 为根的左右子树中，所以 root 就是它们的最近公共祖先 if (left != null & & right != null) return root; // 由于节点 p,q 一定在二叉树中，left和right不会同时为null // 若 left != null & & right == null，说明在左子树中找到 p 或 q，而在右子树找不到 p 或 q，则剩下一个也在左子树 // 所以 left 就是最近公共祖先 // 另一种情况同理 return (left != null) ? left : right;

执行时间：100.00%；内存消耗：91.55%；

9. 二叉搜索树序列 [hard]

文章图片

9.1 考虑点

数组的第一个数必须为顶节点；
与左右节点的插入顺序无关紧要，但子节点的添加一定要在父节点之后；

9.2 解法 9.2.1 回溯法+广度优先遍历

private List< List< Integer> > ans; public List< List< Integer> > BSTSequences(TreeNode root) ans = new ArrayList< > (); List< Integer> path = new ArrayList< > (); // 如果 root==null 返回 [[]] if (root == null) ans.add(path); return ans; List< TreeNode> queue = new LinkedList< > (); queue.add(root); // 开始进行回溯 bfs(queue, path); return ans; // 回溯法+广度优先遍历 private void bfs(List< TreeNode> queue, List< Integer> path) // queue 为空说明遍历完了，可以返回了 if (queue.isEmpty()) ans.add(new ArrayList< > (path)); return; // 将 queue 拷贝一份，用于稍后回溯 List< TreeNode> copy = new ArrayList< > (queue); // 对 queue 进行循环，每循环考虑 “是否「将当前 cur 节点从 queue 中取出并将其左右子 // 节点加入 queue ，然后将 cur.val 加入到 path 末尾」 ” 的情况进行回溯 for (int i = 0; i < queue.size(); i++) TreeNode cur = queue.get(i); path.add(cur.val); queue.remove(i); // 将左右子节点加入队列 if (cur.left != null) queue.add(cur.left); if (cur.right != null) queue.add(cur.right); bfs(queue, path); // 恢复 path 和 queue ，进行回溯 path.remove(path.size() - 1); queue = new ArrayList< > (copy);

执行时间：90.30%；内存消耗：93.98%；
对于这种找出所有情况的题目，回溯法是最容易想到的方法之一了，这道题也可以用回溯法，可以发现刚才选元素的过程和层序遍历的过程其实是一致的：
- 最开始 queue 中只有 12 ，只能选12，将 12 出队并将它的两个子节点入队，得到 [12]；
  选了12之后 queue 中剩下 5、19 ，就从 5 和 19 中选一个，得到 [12,5],[12,19]；
- 如果选了 5 ，将 5 出队并将它的两个子节点入队，那么此时 queue 中剩下 19、2、9，得到 [12,5,2],[12,5,9],[12,5,19]；
- 如果选了 19 ，将 19 出队并将它的子节点入队，那么此时 queue 中剩下 5、15，得到 [12,19,5],[12,19,15]；
- 后续同理；

10. 检查子树 [medium]

文章图片

10.1 考虑点

这里的“万”是干扰的；

10.2 解法 10.2.1 递归法（优）

boolean isFound =false; public boolean checkSubTree(TreeNode t1, TreeNode t2) if(t1 == null) return false; if(t1.val == t2.val) isFound = true; return true; else isFound = false; boolean left; boolean right; if(isFound) left = checkSubTree(t1.left, t2.left); right = checkSubTree(t1.right, t2.right); return left & & right; else left = checkSubTree(t1.left, t2); right = checkSubTree(t1.right, t2); if(left) return checkSubTree(t1.left, t2); if(right) return checkSubTree(t1.right, t2); return false;

执行时间：100.00%；内存消耗：46.52%；

12. 求和路径 [medium]

文章图片

12.1 考虑点

可以使用散列表优化算法，下面解法没给出；

12.2 解法 12.2.1 暴力法（优）

class Solution int res = 0; public int pathSum(TreeNode root, int sum) int dep = depth(root); int[] paths = new int[dep]; pathSum(root, sum, 0, paths); return res; public void pathSum(TreeNode root, int sum, int level, int[] paths) if (root == null) return; paths[level] = root.val; int t = 0; for (int i = level; i > = 0; i--) t += paths[i]; if (t == sum) res += 1; pathSum(root.left, sum, level + 1, paths); pathSum(root.right, sum, level + 1, paths); public int depth(TreeNode root) if (root == null) return 0; return Math.max(depth(root.left), depth(root.right)) + 1;

执行时间：100.00%；内存消耗：69.08%；

12.2.2 回溯法

private int res = 0; public int pathSum(TreeNode root, int sum) if(root == null) return res; helper(root, sum); pathSum(root.left, sum); pathSum(root.right, sum); return res; private void helper(TreeNode node, int sum) if(node == null) return; sum -= node.val; if(sum == 0) res ++; helper(node.left, sum); helper(node.right, sum); sum += node.val;