二叉树

题型5：LCA最近公共祖先

236.二叉树的最近公共祖先（中等）

解题思路：
核心点在于：

  1. 如果当前节点 node 的左右子树各含有 p 或 q 节点，那么 node节点则为 p 和 q 节点的最近公共祖先

  2. 如果当前节点 node 等于 p 或 q 节点，那么当前节点 node 为 p 和 q 节点的最近公共祖先

    递归解法一
    1. class Solution {
    2.  private TreeNode lca;
    4.  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    5.      dfs(root, p, q);
    6.      return lca;
    7.  }
    9.  private int dfs(TreeNode root, TreeNode p, TreeNode q) {
    10.      if(root == null) {
    11.          return 0;
    12.      }
    13.      int leftContains = dfs(root.left, p, q);
    14.      if(lca != null) {
    15.          return 2;
    16.      }
    17.      int rightContains = dfs(root.right, p, q);
    18.      // 剪枝
    19.      if(lca != null) {
    20.          return 2;
    21.      }
    22.      int rootContains = 0;
    23.      if(root == p || root == q) {
    24.          rootContains = 1;
    25.      }
    26.      if(rootContains == 0 && leftContains == 1 && rightContains == 1) {
    27.          lca = root;
    28.      }
    29.      if(rootContains == 1 && (leftContains == 1 || rightContains == 1)) {
    30.          lca = root;
    31.      }
    32.      return rootContains + leftContains + rightContains;
    33.  }
    34. }

递归解法二
  1. class Solution {
  2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.         if(root == null) {
  4.             return null;
  5.         }
  7.         if(root == p || root == q) {
  8.             return root;
  9.         }
  11.         TreeNode lNode = lowestCommonAncestor(root.left, p, q);
  12.         TreeNode rNode = lowestCommonAncestor(root.right, p, q);
  14.         if(lNode != null && rNode != null) {
  15.             return root;
  16.         } else if(lNode == null) {
  17.             return rNode;
  18.         } else {
  19.             return lNode;
  20.         }
  21.     }
  22. }

剑指Offer 68 - I.二叉搜索树的最近公共祖先（中等）

  1. class Solution {
  2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.         while(root != null) {
  4.             if(p.val < root.val && root.val < q.val) {
  5.                 return root;
  6.             } else if(p.val < root.val && q.val < root.val) {
  7.                 root = root.left;
  8.             } else if(p.val > root.val && q.val > root.val) {
  9.                 root = root.right;
  10.             } else {
  11.                 return root;
  12.             }
  13.         }
  14.         return null;
  15.     }
  16. }

题型6：二叉树转单、双、循环链表

114.二叉树展开为链表（中等）

哨兵节点 + 前序遍历
  1. class Solution {
  2.     // 伪头结点
  3.     private TreeNode dumyHead = new TreeNode();
  4.     // 核心点：tail 要设置为 全局变量
  5.     private TreeNode tail = dumyHead;
  7.     public void flatten(TreeNode root) {
  8.         if(root == null) {
  9.             return;
  10.         }
  11.         // 先序遍历
  12.         TreeNode left = root.left;
  13.         TreeNode right = root.right;
  14.         // 往伪头结点插入
  15.         tail.right = root;
  16.         tail = root;
  17.         root.left = null;
  18.         flatten(left);
  19.         flatten(right);
  20.     }
  21. }

后序遍历
  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public void flatten(TreeNode root) {
  18.         if(root == null) {
  19.             return;
  20.         }
  21.         // 后序遍历
  22.         flatten(root.left);
  23.         flatten(root.right);
  25.         TreeNode left = root.left;
  26.         TreeNode right = root.right;
  28.         // 将左子树作为右子树
  29.         root.right = left;
  30.         root.left = null;
  32.         // 将原右子树接至当前右子树的最右端
  33.         TreeNode p = root;
  34.         while(p.right != null) {
  35.             p = p.right;
  36.         }
  37.         p.right = right;
  38.     }
  39. }

面试题17.12. BiNode（中等）

  1. class Solution {
  2.     private TreeNode dumyHead = new TreeNode();
  4.     private TreeNode tail = dumyHead;
  6.     public TreeNode convertBiNode(TreeNode root) {
  7.         inorder(root);
  8.         return dumyHead.right;
  9.     }
  11.     private void inorder(TreeNode root) {
  12.         if(root == null) {
  13.             return;
  14.         }
  15.         inorder(root.left);
  16.         TreeNode right = root.right;
  17.         tail.right = root;
  18.         tail = root;
  19.         tail.left = null;
  20.         inorder(right);
  21.     }
  22. }

剑指Offer 36.二叉搜索树与双向链表（中等）

  1. class Solution {
  2.     private Node head = new Node();
  4.     private Node tail = head;
  6.     public Node treeToDoublyList(Node root) {
  7.         if(root == null) {
  8.             return null;
  9.         }
  10.         // 中序遍历
  11.         inorder(root);
  12.         tail.right = head.right;
  13.         head.right.left = tail;
  14.         return head.right;
  15.     }
  17.     private void inorder(Node node) {
  18.         if(node == null) {
  19.             return;
  20.         }
  21.         inorder(node.left);
  22.         tail.right = node;
  23.         node.left = tail;
  24.         tail = node;
  25.         inorder(node.right);
  26.     }
  27. }

面试题04.03.特定深度节点链表（中等）

队列-层次遍历
  1. class Solution {
  2.     public ListNode[] listOfDepth(TreeNode tree) {
  3.         if(tree == null) {
  4.             return new ListNode[0];
  5.         }
  6.         // 层次遍历
  7.         Queue<TreeNode> queue = new LinkedList<>();
  8.         List<ListNode> res = new ArrayList<>();
  9.         queue.offer(tree);
  10.         while(!queue.isEmpty()) {
  11.             int size = queue.size();
  12.             ListNode dumyHeadNode = new ListNode(), tmp = dumyHeadNode;
  13.             for(int i = 0; i < size; i++) {
  14.                 TreeNode node = queue.poll();
  15.                 tmp.next = new ListNode(node.val);
  16.                 tmp = tmp.next;
  17.                 if(node.left != null) {
  18.                     queue.offer(node.left);
  19.                 }
  20.                 if(node.right != null) {
  21.                     queue.offer(node.right);
  22.                 }
  23.             }
  24.             res.add(dumyHeadNode.next);
  25.         }
  26.         return res.toArray(new ListNode[0]);
  27.     }
  28. }

递归-深度优先遍历
  1. class Solution {
  2.     public ListNode[] listOfDepth(TreeNode tree) {
  3.         List<ListNode> res = new ArrayList<>();
  4.         dfs(tree, res, 0);
  5.         return res.toArray(new ListNode[0]);
  6.     }
  8.     private void dfs(TreeNode root, List<ListNode> res, int level) {
  9.         if(root == null) {
  10.             return;
  11.         }
  12.         ListNode newNode = new ListNode(root.val);
  13.         if(res.size() <= level) {
  14.             res.add(newNode);
  15.         } else {
  16.             // 头插法
  17.             newNode.next = res.get(level);
  18.             res.set(level, newNode);
  19.         }
  20.         // 往右子树向下遍历
  21.         dfs(root.right, res, level + 1);
  22.         dfs(root.left, res, level + 1);
  23.     }
  24. }

题型7：按照遍历结果反向构建二叉树

105.从前序与中序遍历序列构造二叉树（中等）

递归

解题思路：

  1. 在前序遍历数组中，能明确根节点的值。

  2. 结合步骤一，在中序遍历数组中，能明确左右子树的节点范围。

    1. class Solution {
    2.  public TreeNode buildTree(int[] preorder, int[] inorder) {
    3.      // 递归
    4.      return myBuildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    5.  }
    7.  private TreeNode myBuildTree(int[] preorder, int i, int j, int[] inorder, int p, int r) {
    8.      if(i > j) {
    9.          return null;
    10.      }
    11.      int val = preorder[i];
    12.      TreeNode root = new TreeNode(val);
    13.      // 找出根节点在中序遍历数组中的下标
    14.      int rIdx = p;
    15.      while(rIdx <= r && inorder[rIdx] != val) {
    16.          rIdx++;
    17.      }
    18.      // 计算根节点的左子树的节点大小
    19.      int leftTreeSize = rIdx - p;
    20.      TreeNode left = myBuildTree(preorder, i + 1, i + leftTreeSize, inorder, p, rIdx - 1);
    21.      TreeNode right = myBuildTree(preorder, i + leftTreeSize + 1, j, inorder, rIdx + 1, r);
    22.      root.left = left;
    23.      root.right = right;
    24.      return root;
    25.  }
    26. }

889.根据前序和后序遍历构造二叉树（中等）

  1. class Solution {
  2.     public TreeNode constructFromPrePost(int[] pre, int[] post) {
  3.         return buildTree(pre, 0, pre.length - 1, post, 0, post.length - 1);
  4.     }
  6.     private TreeNode buildTree(int[] pre, int preStart, int preEnd, int[] post, int postStart, int postEnd) {
  7.         if(preStart > preEnd) {
  8.             return null;
  9.         }
  10.         TreeNode root = new TreeNode(pre[preStart]);
  11.         if(preStart == preEnd) {
  12.             return root;
  13.         }
  14.         int idx = postStart;
  15.         while(post[idx] != pre[preStart + 1]) {
  16.             idx++;
  17.         }
  18.         int leftTreeSize = idx - postStart;
  20.         TreeNode left = buildTree(pre, preStart + 1, preStart + 1 + leftTreeSize, post, postStart, idx);
  21.         TreeNode right = buildTree(pre, preStart + 1 + leftTreeSize + 1, preEnd, post, idx + 1, postEnd -1);
  23.         root.left = left;
  24.         root.right = right;
  25.         return root;
  26.     }
  27. }

106.从中序与后序遍历序列构造二叉树（中等）

  1. class Solution {
  2.     public TreeNode buildTree(int[] inorder, int[] postorder) {
  3.         return myBuildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
  4.     }
  6.     private TreeNode myBuildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
  7.         if(inStart > inEnd) {
  8.             return null;
  9.         }
  10.         int rootVal = postorder[postEnd];
  11.         TreeNode root = new TreeNode(rootVal);
  12.         if(postStart == postEnd) {
  13.             return root;
  14.         }
  15.         int index = inStart;
  16.         while(inorder[index] != rootVal) {
  17.             index++;
  18.         }
  19.         int leftTreeSize = index - inStart;
  20.         TreeNode left = myBuildTree(inorder, inStart, index - 1, postorder, postStart, postStart + leftTreeSize - 1);
  21.         TreeNode right = myBuildTree(inorder, index + 1, inEnd, postorder, postStart + leftTreeSize, postEnd - 1);
  22.         root.left = left;
  23.         root.right = right;
  24.         return root;
  25.     }
  26. }

剑指Offer 33.二叉搜索树的后序遍历序列（中等）

解题思路：
二叉树前中后序遍历的组成结构：
前序：[ 根节点 | 左子树节点 | 右子树节点 ]
中序：[ 左子树节点 | 根节点 | 右子树节点 ]
后序：[ 左子树节点 | 右子树节点 | 根节点 ]

BST 特性：任意一个节点的值都比其左子树节点的值大，比其右子树节点的值小。

  1. class Solution {
  2.     public boolean verifyPostorder(int[] postorder) {
  3.         return cur(postorder, 0, postorder.length - 1);
  4.     }
  6.     private boolean cur(int[] postorder, int postStart, int postEnd) {
  7.         if(postStart >= postEnd) {
  8.             return true;
  9.         }
  10.         // 根节点值
  11.         int rootVal = postorder[postEnd];
  12.         int idx = postStart;
  13.         // 遍历左子树的值，找出第一个比根节点大的值
  14.         while(idx < postEnd && postorder[idx] < rootVal) {
  15.             idx++;
  16.         }
  17.         // 判断右子树范围内的值，此范围内的值需要比根节点的值大
  18.         for(int i = idx; i < postEnd; i++) {
  19.             if(postorder[i] < rootVal) {
  20.                 return false;
  21.             }
  22.         }
  23.         return cur(postorder, postStart, idx - 1) && cur(postorder, idx, postEnd - 1);
  24.     }
  25. }

题型8：二叉树上的最长路径和

543.二叉树的直径（简单）

递归

解题思路：转换成求树深即可。即比较每个节点的左右子树深度之和，求最大值。

  1. class Solution {
  2.     private int ans = 0;
  3.     public int diameterOfBinaryTree(TreeNode root) {
  4.         if(root == null) {
  5.             return 0;
  6.         }
  7.         maxDepth(root);
  8.         return ans;
  9.     }
  11.     private int maxDepth(TreeNode root) {
  12.         if(root == null) {
  13.             return 0;
  14.         }
  15.         int left = maxDepth(root.left);
  16.         int right = maxDepth(root.right);
  17.         int dia = left + right;
  18.         ans = Math.max(ans, dia);
  19.         return Math.max(left, right) + 1;
  20.     }
  21. }

剑指Offer 34.二叉树中和为某一值的路径（中等）

  1. class Solution {
  2.     public List<List<Integer>> pathSum(TreeNode root, int target) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         dfs(root, res, new ArrayList<Integer>(), target, 0);
  5.         return res;
  6.     }
  8.     private void dfs(TreeNode root, List<List<Integer>> res, List<Integer> path, int target, int pathSum) {
  9.         if(root == null) {
  10.             return;
  11.         }
  12.         pathSum += root.val;
  13.         path.add(root.val);
  14.         // 从树的根节点开始往下一直到叶节点所经过的节点形成一条路径，即必须是到叶子节点
  15.         if(root.left == null && root.right == null && target == pathSum) {
  16.             List<Integer> tmp = new ArrayList<>(path);
  17.             res.add(tmp);
  18.             path.remove(path.size() - 1);
  19.             return;
  20.         }
  21.         dfs(root.left, res, path, target, pathSum);
  22.         dfs(root.right, res, path, target, pathSum);
  23.         path.remove(path.size() - 1);
  24.     }
  25. }

124.二叉树中的最大路径和 （困难）

437. 路径总和III （困难）

堆和Trie

堆

23.合并K个升序链表(困难) （例题）

解题思路：利用优先级队列来构造小顶堆，然后利用小顶堆的特性来实现升序链表

  1. class Solution {
  2.     public ListNode mergeKLists(ListNode[] lists) {
  3.         ListNode dumyHead = new ListNode(), tNode = dumyHead;
  4.         // 利用优先级队列构造小顶堆
  5.         PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((n1, n2) -> n1.val - n2.val);
  7.         // 初始化小顶堆
  8.         for(ListNode node : lists) {
  9.             if(node != null) {
  10.                 queue.offer(node);
  11.             }
  12.         }
  14.         while(!queue.isEmpty()) {
  15.             ListNode node = queue.poll();
  16.             tNode.next = node;
  17.             tNode = node;
  18.             if(node.next != null) {
  19.                 queue.offer(node.next);
  20.             }
  21.         }
  23.         return dumyHead.next;
  24.     }
  25. }

347.前K个高频元素（中等） （例题）

优先级队列 - 大顶堆

解题思路：

  1. 自定类记录数组中不重复元素的值以及其出现的次数。
  2. 使用 HashMap 计算数组中不重复元素的出现次数。

  3. 利用优先级队列构造大顶堆，通过大顶堆的特性，获取前 k 个高频元素。

    1. class Solution {
    2.  class Node {
    3.      private int val;
    5.      private int count;
    7.      public Node(int val, int count) {
    8.          this.val = val;
    9.          this.count = count;
    10.      }
    11.  }
    13.  public int[] topKFrequent(int[] nums, int k) {
    14.      // 利用优先级构造大顶堆
    15.      PriorityQueue<Node> queue = new PriorityQueue<>((n1, n2) -> n2.count - n1.count);
    16.      // 计算频率
    17.      HashMap<Integer, Integer> map = new HashMap<>();
    18.      for(int num : nums) {
    19.          if(map.containsKey(num)) {
    20.              map.put(num, map.get(num) + 1);
    21.          } else {
    22.              map.put(num, 1);
    23.          }
    24.      }
    25.      // 初始化大顶堆
    26.      for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
    27.          queue.offer(new Node(entry.getKey(), entry.getValue()));
    28.      }
    29.      int[] res = new int[k];
    30.      for(int i = 0; i < k; i++) {
    31.          res[i] = queue.poll().val;
    32.      }
    33.      return res;
    34.  }
    35. }

295.数据流的中位数（困难）（例题）

  1. class MedianFinder {
  2.     // 最小堆
  3.     private PriorityQueue<Integer> minHeap;
  4.     // 最大堆
  5.     private PriorityQueue<Integer> maxHeap;
  8.     /** initialize your data structure here. */
  9.     public MedianFinder() {
  10.         this.minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);
  11.         this.maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
  12.     }
  14.     public void addNum(int num) {
  15.         if(maxHeap.isEmpty() || num <= maxHeap.peek()) {
  16.             maxHeap.add(num);
  17.         } else {
  18.             minHeap.add(num);
  19.         }
  20.         // 维持最大堆内元素个数永远只比最小堆内元素个数最多多一个元素。
  21.         while(maxHeap.size() < minHeap.size()) {
  22.             maxHeap.add(minHeap.poll());
  23.         }
  24.         while(minHeap.size() < maxHeap.size() - 1) {
  25.             minHeap.add(maxHeap.poll());
  26.         }
  27.     }
  29.     public double findMedian() {
  30.         if(maxHeap.isEmpty()) {
  31.             return 0;
  32.         }
  33.         if(maxHeap.size() > minHeap.size()) {
  34.             return maxHeap.peek();
  35.         } else {
  36.             return (maxHeap.peek() + minHeap.peek()) / 2f;
  37.         }
  38.     }
  39. }

973.最接近原点的K个点（中等）

优先级队列-小顶堆

解题思路：

  1. 自定义一个类，存储数组 point 和到原点的距离 sqrt
  2. 使用优先级队列，构建小顶堆 minHeap，将数组 points 值全部加入到 minHeap 中

  3. 利用小顶堆的特性，poll 出 k 个元素，即为最接近原点的 k 个点

    1. class Solution {
    2.  class Closest {
    4.      private int[] point;
    6.      private int sqrt;
    8.      public Closest(int[] point, int sqrt) {
    9.          this.point = point;
    10.          this.sqrt = sqrt;
    11.      }
    12.  }
    14.  public int[][] kClosest(int[][] points, int k) {
    15.      // 小顶堆
    16.      PriorityQueue<Closest> queue = new PriorityQueue<>((c1, c2) -> c1.sqrt - c2.sqrt);
    17.      // 初始化小顶堆
    18.      for(int i = 0; i < points.length; i++) {
    19.          int[] point = points[i];
    20.          int x = point[0];
    21.          int y = point[1];
    22.          int sqrt = x * x + y * y;
    23.          queue.offer(new Closest(point, sqrt));
    24.      }
    25.      int[][] res = new int[k][2];
    26.      for(int i = 0; i < k; i++) {
    27.          Closest c = queue.poll();
    28.          res[i] = c.point;
    29.      }
    30.      return res;
    31.  }
    32. }

优先级队列-大顶堆

解题思路：

  • 自定义一个类，存储数组 point 和到原点的距离 sqrt 。
  • 使用优先级队列，构建大顶堆 maxHeap，先将数组 points 中 k 个元素加入到 maxHeap 中。

  • 然后遍历数组 points 中剩余的元素，比 maxHeap 堆顶元素小的，加入 maxHeap，并 poll 出堆顶元素，遍历完毕后，堆内元素即为最接近原点的 k 个点。

    1. class Solution {
    2.   class Closest {
    4.       private int[] point;
    6.       private int sqrt;
    8.       public Closest(int[] point, int sqrt) {
    9.           this.point = point;
    10.           this.sqrt = sqrt;
    11.       }
    12.   }
    14.   public int[][] kClosest(int[][] points, int k) {
    15.       // 构建大顶堆
    16.       PriorityQueue<Closest> maxHeap = new PriorityQueue<>((c1, c2) -> c2.sqrt - c1.sqrt);
    17.       // 初始化大顶堆
    18.       for(int i = 0; i < k; i++) {
    19.           int[] point = points[i];
    20.           int sqrt = sqrt(point);
    21.           maxHeap.offer(new Closest(point, sqrt));
    22.       }
    23.       for(int i = k; i < points.length; i++) {
    24.           int[] point = points[i];
    25.           int sqrt = sqrt(point);
    26.           if(sqrt < maxHeap.peek().sqrt) {
    27.               maxHeap.offer(new Closest(point, sqrt));
    28.               maxHeap.poll();
    29.           }
    30.       }
    31.       int[][] res = new int[k][2];
    32.       for(int i = 0; i < k; i++) {
    33.           Closest c = maxHeap.poll();
    34.           res[i] = c.point;
    35.       }
    36.       return res;
    37.   }
    39.   private int sqrt(int[] point) {
    40.       int x = point[0];
    41.       int y = point[1];
    42.       return x * x + y * y;
    43.   }
    44. }

313.超级丑数（中等）

优先级队-最小堆

解题思路：

  1. class Solution {
  2.     public int nthSuperUglyNumber(int n, int[] primes) {
  3.         PriorityQueue<Long> minHeap = new PriorityQueue<>();
  4.         // 初始化最小堆
  5.         long res = 1;
  6.         for(int i = 1; i < n; i++) {
  7.             for(int prime : primes) {
  8.                 minHeap.add(prime * res);
  9.             }
  10.             res = minHeap.poll();
  11.             while(!minHeap.isEmpty() && res == minHeap.peek()) {
  12.                 minHeap.poll();
  13.             }
  14.         }
  15.         return (int) res;
  16.     }
  17. }


Trie

208.实现Trie (前缀树)（中等） 标准Trie树

  1. class Trie {
  3.     class TreeNode {
  5.         private TreeNode[] children;
  7.         private boolean isEnd;
  9.         public TreeNode() {
  10.             this.children = new TreeNode[26];
  11.             this.isEnd = false;
  12.         }        
  13.     }
  15.     private TreeNode root;
  17.     /** Initialize your data structure here. */
  18.     public Trie() {
  19.         root = new TreeNode();
  20.     }
  22.     /** Inserts a word into the trie. */
  23.     public void insert(String word) {
  24.         char[] array = word.toCharArray();
  25.         TreeNode p = root;
  26.         for(char c : array) {
  27.             int index = hash(c);
  28.             if(p.children[index] == null) {
  29.                 p.children[index] = new TreeNode();
  30.             }
  31.             p = p.children[index];
  32.         }
  33.         p.isEnd = true;
  34.     }
  36.     /** Returns if the word is in the trie. */
  37.     public boolean search(String word) {
  38.         TreeNode p = searchPrefix(word);
  39.         return p != null && p.isEnd;
  40.     }
  42.     /** Returns if there is any word in the trie that starts with the given prefix. */
  43.     public boolean startsWith(String prefix) {
  44.         return searchPrefix(prefix) != null;
  45.     }
  47.     private TreeNode searchPrefix(String word) {
  48.         char[] array = word.toCharArray();
  49.         TreeNode p = root;
  50.         for(char c : array) {
  51.             int index = hash(c);
  52.             if(p.children[index] == null) {
  53.                 return null;
  54.             }
  55.             p = p.children[index];
  56.         }
  57.         return p;
  58.     }
  60.     private int hash(char c) {
  61.         return c - 'a';
  62.     }
  63. }
  65. /**
  66.  * Your Trie object will be instantiated and called as such:
  67.  * Trie obj = new Trie();
  68.  * obj.insert(word);
  69.  * boolean param_2 = obj.search(word);
  70.  * boolean param_3 = obj.startsWith(prefix);
  71.  */

以下为选做题目：

面试题17.17.多次搜索（中等） 标准AC自动机，不过写AC自动机太复杂，Trie树搞定

212.单词搜索II（困难）