面试题：C++ 递归函数终止条件在树形结构遍历中的优化

Question

假设给定一个树形结构（可以自行定义树节点结构），要求使用递归函数进行深度优先遍历。在遍历过程中，根据节点的某些属性（例如节点值大于特定阈值）来设计递归的终止条件，以优化遍历过程，避免不必要的递归调用。请实现这个递归函数，并详细阐述终止条件的设计思路以及对整体性能的影响。

Answer 1

1. 定义树节点结构

假设树节点存储一个整数值，使用Python语言，定义如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

2. 实现递归的深度优先遍历函数

def dfs(root, threshold):
    result = []
    def recursive_helper(node):
        # 终止条件：节点为空或者节点值大于阈值
        if not node or node.val > threshold:
            return
        result.append(node.val)
        recursive_helper(node.left)
        recursive_helper(node.right)
    recursive_helper(root)
    return result

3. 终止条件的设计思路

• 节点为空：这是常规的树遍历终止条件。当到达叶子节点的子节点（即空节点）时，继续向下遍历没有意义，所以直接返回。
• 节点值大于阈值：这是为了优化遍历过程而添加的条件。当节点值大于特定阈值时，根据题目要求，不再需要对该节点的子树进行遍历，因为我们已经知道这部分子树不符合我们的某种业务逻辑（由阈值判断定义），这样可以提前终止递归，避免不必要的计算。

4. 对整体性能的影响

• 时间复杂度优化：在理想情况下，如果树结构中有大量节点的值大于阈值，通过提前终止递归，可以显著减少递归调用的次数，从而降低时间复杂度。原本可能需要遍历整个树的所有节点（时间复杂度为$O(n)$，$n$为树的节点数），现在可能只需要遍历部分节点，时间复杂度可能会降低到$O(k)$，$k$为实际遍历的节点数，且$k < n$。
• 空间复杂度优化：由于递归调用次数减少，栈空间的使用也会相应减少。递归调用在栈中保存函数的调用状态，提前终止递归意味着栈中保存的状态数量减少，从而对空间复杂度也有一定程度的优化。特别是对于深度较大的树，这种优化效果可能更为明显。