leetcode 623 Add One Row to Tree

迷南。 2022-06-13 02:39 110阅读 0赞

# 1.题目 #

Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.  
给一棵二叉树的根结点root，值v，深度d。你需要给这棵树添加一层深度为d值为v的节点。  
注意根结点深度为1  
添加规则：  
对于深度为d-1的非空节点N，为该节点创建两个值为v的左右子节点newleft,newright，然后将N原本的左子树根结点oldleft作为N的新左节点的左节点，N原本的右子树根结点oldright作为N的新右节点的右节点。  
如果d=1，那么创建一个值为v的节点作为整棵树的根结点，原来的根结点作为新的根结点的左子树根结点。

Example 1:  
Input:  
A binary tree as following:

4
       /   \
      2     6
     / \   / 
    3   1 5

v = 1 d = 2

Output:

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

Example 2:  
Input:  
A binary tree as following:

4
     /   
    2    
    / \   
    3  1

v = 1 d = 3

Output:

4
      /   
     2
    / \    
    1  1
    /   \  
    3    1

Note:  
The given d is in range \[1, maximum depth of the given tree + 1\].  
The given binary tree has at least one tree node.

# 2.分析 #

考察树的广度优先遍历。用queue实现。

# 3.代码 #

class Solution {
    public:
        TreeNode* addOneRow(TreeNode* root, int v, int d) {
            if (d == 1)
            {
                TreeNode* node = new TreeNode(v);
                node->left = root;
                root = node;
                return root;
            }
            queue<TreeNode*> nodes;
            nodes.push(root);
            int level = 1;
            while (!nodes.empty()) {
                int size = nodes.size();
                for (int i = 0; i < size; i++) {
                    TreeNode* tmp = nodes.front();
                    nodes.pop();
                    if (level == d - 1) {
                        TreeNode* newleft = new TreeNode(v);
                        TreeNode* newright = new TreeNode(v);
                        newleft->left = tmp->left;
                        newright->right = tmp->right;
                        tmp->left = newleft;
                        tmp->right = newright;
                    }
                    else {
                        if (tmp->left)
                            nodes.push(tmp->left);
                        if (tmp->right)
                            nodes.push(tmp->right);
                    }
                }
                level += 1;
            }
            return root;
        }
    };