C C++ LeetCode题解在二叉树中增加一行示例详解

C C++ LeetCode题解在二叉树中增加一行示例详解

在二叉树中增加一行的题目通常会让很多人头疼，本文将为大家提供一个详细而完整的攻略，同时提供两条示例说明。

题目描述

给定一个二叉树，根节点为第1层，现在要在第d层插入一个值为v的节点，使得原来的树变成新的树。插入完之后，新节点应该在原来第d层节点的左子树的位置上。

解题思路

一般情况下，我们可以采用递归或者BFS方式进行遍历，找到第d层的节点后，将该节点的左右子树分别设为新节点和原来的子树即可。

代码实现

C++代码实现如下：

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if(d == 1) {
            TreeNode* newRoot = new TreeNode(v);
            newRoot -> left = root;
            return newRoot;
        }
        DFS(root,v,d);
        return root;
    }

private:
    void DFS(TreeNode* root, int v, int d) {
        if(root == NULL) return;
        if(d == 2) {
            TreeNode* leftNode = new TreeNode(v);
            TreeNode* rightNode = new TreeNode(v);
            leftNode -> left = root -> left;
            rightNode -> right = root -> right;
            root -> left =leftNode;
            root -> right =rightNode;
            return;
        }
        DFS(root -> left, v, d - 1);
        DFS(root -> right, v, d - 1);
        return;
    }
};

示例说明

以下是两条示例说明：

示例 1

二叉树：

     4
   /   \
  2     6
 / \   / \
3   1 5   7

插入值为v=1，插入层数为d=2。则修改后的二叉树为：

     4
    / \
   1   1
  / \ / \
 2  6 5  7
/ \
3   1

示例 2

二叉树：

      4
     / \
    2   6
   / \
  3   1

插入值为v=1，插入层数为d=3。则修改后的二叉树为：

      4
     / \
    2   6
   / \
  1   1
 /     \
3       1

总结

以上就是本题的详细解答过程，如果您还有其他问题或者疑虑，欢迎在评论区留言，我们将第一时间回答您的疑问。