LeetCode_二叉树_中等_623.在二叉树中增加一行

以你之姓@ 2023-10-06 23:40 19阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

注意，根节点 root 位于深度 1 。

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

**示例 1：**  
![在这里插入图片描述][c9c946c7edf44356bc8fb53c5b0d09c7.png]  
输入: root = \[4,2,6,3,1,5\], val = 1, depth = 2  
输出: \[4,1,1,2,null,null,6,3,1,5\]

**示例 2：**  
![在这里插入图片描述][9708c8d535194fd5af7f3181cf9acfa1.png]  
输入: root = \[4,2,null,3,1\], val = 1, depth = 3  
输出: \[4,2,null,1,1,3,null,null,1\]

**提示：**  
节点数在 \[1, 104\] 范围内  
树的深度在 \[1, 104\]范围内  
\-100 <= Node.val <= 100  
\-105 <= val <= 105  
1 <= depth <= the depth of tree + 1

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/add-one-row-to-tree

## 2.思路 ##

（1）BFS  
每遍历每一层时，用变量 curDepth 来记录当前深度，当 curDepth == depth - 1 时，说明下一层为要添加节点的层，此时便进行添加操作。

（2）DFS  
同理，使用 DFS 时用变量 curDepth 来记录当前深度，到达第 depth - 1 层时，进行添加操作。

## 3.代码实现（Java） ##

//思路1————BFS
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public TreeNode addOneRow(TreeNode root, int val, int depth) {
        
            if (depth == 1) {
        
                return new TreeNode(val, root, null);
            }
            //BFS
            Deque<TreeNode> deque = new ArrayDeque<>();
            deque.addLast(root);
            int curDepth = 1;
            while (!deque.isEmpty()) {
        
                // levelSize 记录当前层的节点数量
                int levelSize = deque.size();
                while (levelSize > 0) {
        
                    //取出队首节点
                    TreeNode curNode = deque.poll();
                    if (curDepth == depth - 1) {
        
                        //下一层为要添加节点的层
                        TreeNode node1 = new TreeNode(val);
                        TreeNode node2 = new TreeNode(val);
                        node1.left = curNode.left;
                        node2.right = curNode.right;
                        curNode.left = node1;
                        curNode.right = node2;
                    } else {
        
                        if (curNode.left != null) {
        
                            deque.addLast(curNode.left);
                        }
                        if (curNode.right != null) {
        
                            deque.addLast(curNode.right);
                        }
                    }
                    levelSize--;
                }
                curDepth++;
            }
            return root;
        }
    }

//思路2————DFS
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public TreeNode addOneRow(TreeNode root, int val, int depth) {
        
            if (depth == 1) {
        
                return new TreeNode(val, root, null);
            }
            dfs(root, 1, val, depth);
            return root;
        }
    
        public void dfs(TreeNode root, int curDepth, int val, int depth) {
        
            if (root == null) {
        
                return;
            }
            if (curDepth == depth - 1) {
        
                 //下一层为要添加节点的层
                TreeNode node1 = new TreeNode(val);
                TreeNode node2 = new TreeNode(val);
                node1.left = root.left;
                node2.right = root.right;
                root.left = node1;
                root.right = node2;
            } else {
        
                dfs(root.left, curDepth + 1, val, depth);
                dfs(root.right, curDepth + 1, val, depth);
            }
        }
    }

[c9c946c7edf44356bc8fb53c5b0d09c7.png]: https://img-blog.csdnimg.cn/c9c946c7edf44356bc8fb53c5b0d09c7.png
[9708c8d535194fd5af7f3181cf9acfa1.png]: https://img-blog.csdnimg.cn/9708c8d535194fd5af7f3181cf9acfa1.png