LETCode 623 : 1行をツリー[ソリューション]に追加する


この質問はこれを解決するための複数の方法で単純な問題から成ります.閉じるこの動画はお気に入りから削除されています.質問は多くのエッジケースを持っているようではありませんので、例のテストケースに対して正しい答えを得ている場合は、それらに少しのバリエーションは、あなたの提出を簡単に承認されます.
難易度:中
ジャンプします
  • Problem Statement
  • Explanation
  • Solution
  • Implementation

  • 問題声明

    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.

    The adding rule is: given a positive integer depth d , for each NOT null tree nodes N in depth d-1 , create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root's left subtree.

    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:

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


    解説

    So the problem is quite simple, You are given a non-empty binary tree and a value v which needs to be inserted as a child at depth d for all non-empty parent nodes. The new node will be at both left and right edge of the parent. The child nodes/subtree of the parent need to be set as the child of the newly created node with the same direction left/right. This should be clear with the given examples.



    解決策

    We are going to do only the below things:

    1. If depth=1 i.e. we need to add the value at root, then we just need to create a new node with value v and make the current root its left child and return the pointer to the new node.
    2. We need to traverse the tree in both directions (left/right) till we reach the depth d-1 . Let's say we are at the node parent , this is the node below which the new nodes need to be added.
    3. Now we need to create a new node for the left subtree of parent so this new node's left pointer will point to the left subtree of parent and then we'll make parent 's left pointer point to the new node. That's how we have added a node between the parent and left subtree.
    4. Same needs to be done for the right subtree.

    As we'll be going down to the tree, we can call it DFS(Depth First Search) based on recursion. So Time Complexity: of this solution may go to O(n) as we might need to add the nodes below the leaf. As recursion uses stack so the Space Complexity: can be O(n) in the worst case.



    実装

    C++ Code:

    class Solution {
    public:
        TreeNode* addOneRow(TreeNode* root, int v, int d) {
            // If need to add the row on root
            if(d==1){
                // Just create a new node with value v 
                // and current root as left child
                TreeNode *ptr = new TreeNode(v, root, nullptr);
                return ptr;
            }
    
            // Traverse down to the parent node at depth d-1
            // to add row at depth d(>1)
            addRow(root, v, d-1);
    
            // Return same pointer root with modified tree
            return root;
        }
    
        // Function to traverse down to the depth d-1 and add row
        void addRow(TreeNode* parent, int v, int dep){
            // If node is NULL the do nothing
            if(!parent)
                return;
    
            // If we have reached depth d-1 i.e. dep=1
            if(dep==1){
                TreeNode *temp;
    
                // Store left ptr
                temp = parent->left; 
                // Replace left ptr with new node with value v
                parent->left = new TreeNode(v);
                // Set stored left pointer as new node's left ptr
                parent->left->left = temp;
    
                // Store right ptr
                temp = parent->right;
                // Replace right ptr with new node with value v
                parent->right = new TreeNode(v);
                // Set stored right pointer as new node's right ptr
                parent->right->right = temp;
            }
            // Else go deeper
            else{
                addRow(parent->left, v, dep-1);
                addRow(parent->right, v, dep-1);
            }
        }
    };
    

    Runnable C++ Code: