[LeetCode] 623. Add One Row to Tree

https://leetcode.com/problems/add-one-row-to-tree/description/

LeetCode - Add One Row to Tree

문제 유형 : 이진트리, dfs, 재귀

문제 난이도 : Medium

 

문제

Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth depth.

Note that the root node is at depth 1.

The adding rule is:

• Given the integer depth, for each not null tree node cur at the depth depth - 1, create two tree nodes with value val as cur's left subtree root and right subtree root.
• cur's original left subtree should be the left subtree of the new left subtree root.
• cur's original right subtree should be the right subtree of the new right subtree root.
• If depth == 1 that means there is no depth depth - 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root's left subtree.

 

이진 트리의 루트랑, 두 정수 val과 depth가 주어집니다.

depth번째 열에 val 의 값을 가진 열(노드들)을 추가하시오.

루트 노드가 깊이 1임을 알아야 합니다.

 

풀이

재귀적으로 순회하면서, depth-1번째의 깊이에서 자식 노드 사이에 새 노드들을 만들어 추가하면 된다.

만약 현재 깊이가 depth-1이면, 새 노드를 만들어 양쪽의 자식으로 추가한다.

새 노드들의 자식들로 기존 자식들을 연결한다.

왼쪽이면 계속 왼쪽자식, 오른쪽이면 계속 오른쪽자식으로 한다.

 

코드

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#pragma GCC optimize("03", "unroll-loops");

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
class Solution {
private:
    int val;
public:
    void solve(TreeNode* root, int depth) {
        if(depth == 1) {
            TreeNode* newLeft = new TreeNode(val, root -> left, NULL);
            root -> left = newLeft;

            TreeNode* newRight = new TreeNode(val, NULL, root -> right);
            root -> right = newRight;
        }

        if(root -> left) {
            solve(root -> left, depth-1);
        }

        if(root -> right) {
            solve(root -> right, depth-1);
        }
    }

    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        this -> val = val;
        if(depth == 1) {
            TreeNode* newNode = new TreeNode(val, root, NULL);
            return newNode;
        }
        solve(root, depth-1);
        return root;
    }
};