C#中如何从二叉树深度优先搜索过渡到迭代加深搜索

实现逻辑非常简单，不需要提前计算整棵树的最大高度，也不需要手动维护递归栈，只需要把你原有的无界DFS拆成「带深度限制的单次遍历」+「逐层提高深度上限的外层循环」两个部分即可，完全贴合你原来代码的遍历顺序。

核心实现拆解 #

• 受限深度前序遍历模块
  给原有DFS逻辑增加两个判断维度：当前节点所在的深度、当前轮次允许抵达的最大深度上限。
  碰到空节点直接返回；如果当前深度超过设置的上限，直接剪枝不再往下递归；没超上限就和原有逻辑一样输出节点值，再递归遍历左右子节点。
• 逐层加深的外层循环模块
  从根节点所在的最上层深度开始，逐轮提高深度上限，调用上面的受限遍历方法。直到某一轮遍历全程没有碰到任何有效节点，说明已经遍历完树的所有层，直接终止循环。逐轮提高深度上限的过程不会一次性探到树的最深处，不会因为树过深出现栈溢出。

完整替换代码 #

直接替换你原有的Node类中DFS相关的实现即可，遍历输出的顺序和你原来写的前序DFS完全对齐：

class Node
{
    public Node Left { get; set; }
    public Node Right { get; set; }
    public int value { get; set; }

    // IDDFS入口方法，替换原有DepthFirst方法
    public void IterativeDeepeningDFS(Node root)
    {
        if (root == null) return;
        int depthLimit = 0;
        while (true)
        {
            // 每跑完一轮受限遍历，检查是否实际访问到了节点
            bool hasTraversedAnyNode = LimitedPreOrderTraverse(root, currentDepth: 0, depthLimit);
            // 这一轮一个节点都没访问到，说明已经超出树的最大深度，直接退出
            if (!hasTraversedAnyNode)
                break;
            // 加深下一轮的深度上限
            depthLimit++;
        }
    }

    // 带深度限制的前序遍历，返回值代表本次遍历是否访问到了有效节点
    private bool LimitedPreOrderTraverse(Node node, int currentDepth, int depthLimit)
    {
        // 空节点直接返回，不算有效访问
        if (node == null)
            return false;
        // 当前深度超过限制，剪枝返回
        if (currentDepth > depthLimit)
            return false;
        
        // 和原有逻辑一致，先输出当前节点值
        Console.WriteLine(node.value + " ");
        
        // 递归遍历左右子树，深度逐层+1
        LimitedPreOrderTraverse(node.Left, currentDepth + 1, depthLimit);
        LimitedPreOrderTraverse(node.Right, currentDepth + 1, depthLimit);
        
        // 走到这里说明当前节点已经被访问，返回true
        return true;
    }
}

常见注意点 #

• 深度计数规则：这里把根节点所在层算作深度0，如果你的项目习惯把根节点计为深度1，只要把初始的depthLimit值改成1，递归初始传入的currentDepth改成1即可，核心逻辑不需要变动。
• IDDFS的固有特性：逐轮加深的过程中会重复访问上层节点（比如深度0轮输出根节点，深度1轮会再输出一次根节点+下一层节点），这是IDDFS本身的机制决定的。如果不希望重复输出节点，只需要在类里加一个HashSet<int>记录已经输出过的节点值，碰到重复的就跳过输出步骤即可，不会破坏整体遍历逻辑。
• 栈溢出规避：因为每一轮受限遍历的递归深度不会超过当前设置的深度上限，就算是非常深的偏斜二叉树，也不会出现一次性递归几百上千层导致的栈溢出问题，这也是IDDFS相比普通无界DFS的核心优势。

内容的提问来源于stack exchange，提问作者G3n1t0