本文共 2096 字，大约阅读时间需要 6 分钟。

二叉树第k层节点数目的求解方法

在处理二叉树的层次问题时，通常需要计算某一特定层数的节点数。这里我们将详细探讨两种常用的方法：深度优先搜索（DFS）和广度优先搜索（BFS），并分析它们的优缺点。

深度优先搜索（DFS）

方法思路：

DFS是一种递归方法，通过遍历每个节点的左子节点和右子节点来逐层深入树结构。我们可以在遍历过程中记录当前深度，当达到目标层数时，增加计数器。

代码实现示例：

public class Solution {
    private int res;
    public int kthfloorNode(TreeNode root, int k) {
        dfs(root, k, 1);
        return res;
    }
    private void dfs(TreeNode root, int targetDepth, int curDepth) {
        if (root == null) {
            return;
        }
        if (curDepth == targetDepth) {
            res++;
            return;
        }
        dfs(root.left, targetDepth, curDepth + 1);
        dfs(root.right, targetDepth, curDepth + 1);
    }
}
class TreeNode {
    int val;
    TreeNode left, right;
    public TreeNode(int val) {
        this.val = val;
    }
}

优点：

直观简洁：DFS的代码逻辑简单易懂，直接通过递归实现层数判断。

时间复杂度：O(n)，每个节点只被访问一次。

空间复杂度：O(min(h, k))，递归深度受限制，避免递归深度过深引起的栈溢出问题。

缺点：

递归深度限制：当目标层数k较大时，可能导致递归深度过深，从而引起栈溢出。

广度优先搜索（BFS）

方法思路：

BFS通过使用队列来逐层处理节点，确保每一层的所有节点都被处理后再处理下一层。这种方法避免了递归深度的问题，适合处理较大的层数。

代码实现示例：

import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public int kthfloorNode(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        Queue
   
     queue = new LinkedList<>();
        queue.offer(root);
        int floor = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            if (floor == k) {
                return size;
            }
            for (int i = 0; i < size; i++) {
                TreeNode x = queue.poll();
                if (x.left != null) {
                    queue.offer(x.left);
                }
                if (x.right != null) {
                    queue.offer(x.right);
                }
            }
            floor++;
        }
        return 0;
    }
}
   

优点：

避免递归深度问题：BFS通过队列处理，避免了递归深度过大的问题，适合处理较大的k值。

时间复杂度：O(n)，每个节点被访问一次。

空间复杂度：O(min(h, k))，队列的最大规模受层数限制。

缺点：

代码复杂度：BFS的实现相对较为复杂，需要使用队列数据结构。

内存消耗：可能占用更多内存资源来存储队列中的节点。

选择方法的依据

• k较小的情况：DFS更为高效，代码简洁。
• k较大情况：BFS更为稳定，避免递归深度过深的问题。

总结

两种方法各有优缺点，选择取决于具体需求。如果你需要处理较大的k值，BFS可能更适合；反之，DFS在k较小时表现更优。

转载地址：http://fhds.baihongyu.com/