搜索-遍历

  • 每个节点要访问一次
  • 每个节点仅访问一次

  • 对于节点的访问顺序不同

    1. -深度优先 `dfs` <br />      -广度优先 `bfs` <br />      -优先级优先

    dfs代码模板(递归)

    ```java public List> levelOrder(TreeNode root) {

    1.   List<List<Integer>> allResults = new ArrayList<>();
    3.   if(root == null){
    4.       return allResults;
    5.   }
    6.   travel(root, 0, allResults);
    7.   return allResults;

    }

  1. private void travel(TreeNode root, int level, List<List<Integer>> results){
  2.     //递归退出条件
  3.     if(results.size() == level){
  4.         results.add(new ArrayList<>());
  5.     }
  6.     results.get(level).add(root.val);
  7.     if(root.left != null){
  8.         travel(root.left, level+1, results);
  9.     }
  10.     if(root.right != null){
  11.         travel(root.right, level+1, results);
  12.     }
  13. }
  1. <a name="Xy0gF"></a>
  2. ### bfs代码模板（队列）
  3. ```java
  4. public class TreeNode {
  5.     int val;
  6.     TreeNode left;
  7.     TreeNode right;
  9.     TreeNode(int x) {
  10.         val = x;
  11.     }
  12. }
  14. public List<List<Integer>> levelOrder(TreeNode root) {
  15.     List<List<Integer>> allResults = new ArrayList<>();
  16.     if (root == null) {
  17.         return allResults;
  18.     }
  19.     Queue<TreeNode> nodes = new LinkedList<>();
  20.     nodes.add(root);
  21.     while (!nodes.isEmpty()) {
  22.         int size = nodes.size();
  23.         List<Integer> results = new ArrayList<>();
  24.         for (int i = 0; i < size; i++) {
  25.             TreeNode node = nodes.poll();
  26.             results.add(node.val);
  27.             if (node.left != null) {
  28.                 nodes.add(node.left);
  29.             }
  30.             if (node.right != null) {
  31.                 nodes.add(node.right);
  32.             }
  33.         }
  34.         allResults.add(results);
  35.     }
  36.     return allResults;
  37. }

LeetCode题目

  1. 二叉树的层序遍历
  2. 括号生成
  3. 在每个树行中找最大值
  4. 岛屿数量