Medium

题目描述

给定一个二叉树的根节点 root 和两个整数 val 和 depth，在给定的深度 depth 处添加一行值为 val 的节点。

注意根节点的深度为 1。

添加规则如下：

  • 给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
  • cur 原来的左子树应该是新左子树根的左子树。
  • cur 原来的右子树应该是新右子树根的右子树。
  • 如果 depth == 1，那意味着根本没有深度为 depth - 1 的节点，则创建一个值为 val 的树节点作为整个原始树的新根，而原始树就是新根的左子树。

示例 1：

输入：root = [4,2,6,3,1,5], val = 1, depth = 2
输出：[4,1,1,2,null,null,6,3,1,5]

示例 2：

输入：root = [4,2,null,3,1], val = 1, depth = 3
输出：[4,2,null,1,1,3,null,null,1]

约束条件：

  • 树中节点数目在范围 [1, 10^4] 内
  • 树的深度在范围 [1, 10^4] 内
  • -100 <= Node.val <= 100
  • -10^5 <= val <= 10^5
  • 1 <= depth <= 树的深度 + 1

解题思路

这道题需要在二叉树的指定深度插入一行新节点。我们需要分情况讨论：

特殊情况处理：

  • 当 depth == 1 时，需要创建新的根节点，原树作为新根的左子树

一般情况处理：

  • 找到深度为 depth - 1 的所有节点
  • 为每个节点创建新的左右子节点，值为 val
  • 将原来的左右子树分别连接到新节点上

解法选择：

  1. DFS递归解法：通过递归遍历到目标深度的前一层，然后插入新节点
  2. BFS层序遍历：逐层遍历直到目标深度的前一层，然后批量插入

推荐使用DFS递归解法，代码更简洁清晰。递归时维护当前深度，当到达 depth - 1 时执行插入操作。对于每个需要插入的位置，创建新节点并正确连接原有的子树。

代码实现

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if (depth == 1) {
            TreeNode* newRoot = new TreeNode(val);
            newRoot->left = root;
            return newRoot;
        }
        
        dfs(root, val, depth, 1);
        return root;
    }
    
private:
    void dfs(TreeNode* node, int val, int depth, int currentDepth) {
        if (!node) return;
        
        if (currentDepth == depth - 1) {
            TreeNode* newLeft = new TreeNode(val);
            TreeNode* newRight = new TreeNode(val);
            
            newLeft->left = node->left;
            newRight->right = node->right;
            
            node->left = newLeft;
            node->right = newRight;
            return;
        }
        
        dfs(node->left, val, depth, currentDepth + 1);
        dfs(node->right, val, depth, currentDepth + 1);
    }
};

class Solution:
    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
        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:
                new_left = TreeNode(val)
                new_right = TreeNode(val)
                
                new_left.left = node.left
                new_right.right = node.right
                
                node.left = new_left
                node.right = new_right
                return
            
            dfs(node.left, current_depth + 1)
            dfs(node.right, current_depth + 1)
        
        dfs(root, 1)
        return root

public class Solution {
    public TreeNode AddOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode newRoot = new TreeNode(val);
            newRoot.left = root;
            return newRoot;
        }
        
        DFS(root, val, depth, 1);
        return root;
    }
    
    private void DFS(TreeNode node, int val, int depth, int currentDepth) {
        if (node == null) return;
        
        if (currentDepth == depth - 1) {
            TreeNode newLeft = new TreeNode(val);
            TreeNode newRight = new TreeNode(val);
            
            newLeft.left = node.left;
            newRight.right = node.right;
            
            node.left = newLeft;
            node.right = newRight;
            return;
        }
        
        DFS(node.left, val, depth, currentDepth + 1);
        DFS(node.right, val, depth, currentDepth + 1);
    }
}

var addOneRow = function(root, val, depth) {
    if (depth === 1) {
        return new TreeNode(val, root, null);
    }
    
    function dfs(node, currentDepth) {
        if (!node) return;
        
        if (currentDepth === depth - 1) {
            const newLeft = new TreeNode(val, node.left, null);
            const newRight = new TreeNode(val, null, node.right);
            node.left = newLeft;
            node.right = newRight;
        } else {
            dfs(node.left, currentDepth + 1);
            dfs(node.right, currentDepth + 1);
        }
    }
    
    dfs(root, 1);
    return root;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型DFS解法
时间复杂度O(n)
空间复杂度O(h)

其中 n 是树中节点的数量，h 是树的高度。在最坏情况下（完全不平衡的树），空间复杂度为 O(n)。