题目

类型：DFS、BFS、二叉树
image.png

解题思路

1、BFS需要用到层序遍历的代码框架

  1. // 输入一棵二叉树的根节点，层序遍历这棵二叉树
  2. void levelTraverse(TreeNode root) {
  3.     if (root == null) return;
  4.     Queue<TreeNode> q = new LinkedList<>();
  5.     q.offer(root);
  7.     // 从上到下遍历二叉树的每一层
  8.     while (!q.isEmpty()) {
  9.         int sz = q.size();
  10.         // 从左到右遍历每一层的每个节点
  11.         for (int i = 0; i < sz; i++) {
  12.             TreeNode cur = q.poll();
  13.             // 将下一层节点放入队列
  14.             if (cur.left != null) {
  15.                 q.offer(cur.left);
  16.             }
  17.             if (cur.right != null) {
  18.                 q.offer(cur.right);
  19.             }
  20.         }
  21.     }
  22. }

2、DFS还是分解问题即可

代码

  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.  */
  17. /**
  18.  * 515. 在每个树行中找最大值
  19.  */
  20. public class FindLargestValueInEachTreeRow {
  21.     //---------------------------------BFS版本---------------------------------
  23.     public List<Integer> largestValues(TreeNode root) {
  24.         List<Integer> res = new LinkedList<>();
  25.         if (root == null) {
  26.             return res;
  27.         }
  29.         Queue<TreeNode> q = new LinkedList<>();
  30.         q.offer(root);
  31.         // while 循环控制从上向下一层层遍历
  32.         while (!q.isEmpty()) {
  33.             int sz = q.size();
  34.             // 记录这一层的最大值
  35.             int levelMax = Integer.MIN_VALUE;
  36.             // for 循环控制每一层从左向右遍历
  37.             for (int i = 0; i < sz; i++) {
  38.                 TreeNode cur = q.poll();
  39.                 levelMax = Math.max(levelMax, cur.val);
  40.                 if (cur.left != null)
  41.                     q.offer(cur.left);
  42.                 if (cur.right != null)
  43.                     q.offer(cur.right);
  44.             }
  45.             res.add(levelMax);
  46.         }
  47.         return res;
  48.     }
  52.     //---------------------------------DFS版本---------------------------------
  54.     ArrayList<Integer> res = new ArrayList<>();
  56.     public List<Integer> largestValuesDFS(TreeNode root) {
  58.         if (root == null) {
  59.             return res;
  60.         }
  61.         traverse(root, 0);
  62.         return res;
  63.     }
  65.     // 遍历二叉树
  66.     public void traverse(TreeNode root, int depth) {
  67.         if (root == null) {
  68.             return;
  69.         }
  70.         if (res.size() <= depth) {
  71.             res.add(root.val);
  72.         } else {
  73.             // 记录当前行的最大值
  74.             res.set(depth, Math.max(res.get(depth), root.val));
  75.         }
  76.         traverse(root.left, depth + 1);
  77.         traverse(root.right, depth + 1);
  78.     }
  79. }