在二叉树中增加一行：挑战与成长

大家好，我是头条X，今天想和大家分享一个编程挑战的故事。最近在简书上看到一个热搜题目：在二叉树中增加一行，这是一道中等难度的算法题。作为一个热爱编程的程序员，我决定挑战一下自己，看看能否在有限的时间内解决这个问题。

题目背景

题目描述如下：给定一个二叉树的根节点 root 和两个整数 val 和 depth，在第 depth 行插入值为 val 的节点。具体来说，如果 depth 为 1，则将新节点作为新的根节点，原来的根节点作为新根节点的左子树。如果 depth 大于 1，则在第 depth - 1 层的所有节点下插入新节点。

解题思路

首先，我们需要理解题目要求。题目要求我们在指定的深度插入新节点，这意味着我们需要遍历树到指定的深度。我们可以使用递归或迭代的方法来实现这一点。

递归方法

递归方法的核心思想是通过递归函数来遍历树，直到到达指定的深度。具体步骤如下：

• 如果当前深度等于目标深度减一，说明我们已经到达了需要插入新节点的位置。
• 创建新的节点，并将当前节点的左右子树分别作为新节点的左右子树。
• 继续递归处理当前节点的左右子树。

递归方法的代码如下：

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

def addOneRow(root, val, depth):
    if depth == 1:
        new_root = TreeNode(val)
        new_root.left = root
        return new_root

    def dfs(node, current_depth):
        if not node:
            return
        if current_depth == depth - 1:
            left_node = TreeNode(val)
            right_node = TreeNode(val)
            left_node.left = node.left
            right_node.right = node.right
            node.left = left_node
            node.right = right_node
        else:
            dfs(node.left, current_depth + 1)
            dfs(node.right, current_depth + 1)

    dfs(root, 1)
    return root

迭代方法

迭代方法的核心思想是使用队列来进行层次遍历，直到到达指定的深度。具体步骤如下：

• 初始化一个队列，将根节点加入队列。
• 使用一个变量记录当前的深度，从 1 开始。
• 当当前深度小于目标深度减一时，继续遍历队列中的节点，并将它们的子节点加入队列。
• 当当前深度等于目标深度减一时，遍历队列中的所有节点，为每个节点插入新的子节点。

迭代方法的代码如下：

from collections import deque

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

def addOneRow(root, val, depth):
    if depth == 1:
        new_root = TreeNode(val)
        new_root.left = root
        return new_root

    queue = deque([root])
    current_depth = 1

    while current_depth < depth - 1:
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        current_depth += 1

    for node in queue:
        left_node = TreeNode(val)
        right_node = TreeNode(val)
        left_node.left = node.left
        right_node.right = node.right
        node.left = left_node
        node.right = right_node

    return root

实战体验

在实际编码过程中，我发现递归方法更加直观，代码也更加简洁。然而，对于大规模的树，递归可能会导致栈溢出，因此在实际应用中，迭代方法更加稳健。

我在 LeetCode 上提交了这两种方法，都顺利通过了所有测试用例。这个过程不仅让我对二叉树的操作有了更深的理解，也让我体会到了编程的乐趣。

总结与反思

通过这次挑战，我学到了很多。首先，理解题目要求是解决问题的关键。其次，选择合适的数据结构和算法能够显著提高效率。最后，多尝试不同的方法，可以帮助我们更好地理解和掌握问题。

如果你也对这道题目感兴趣，不妨动手试一试。编程不仅仅是解决问题，更是一种思维方式的锻炼。希望我的分享对你有所帮助，如果有任何问题或建议，欢迎在评论区留言交流。