솔루션: 트리에 행 하나 추가

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #623(중간): 트리에 하나의 행 추가

설명:

(다음으로 이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

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: v = 1 d = 2
Output:

Example 2:
Input:	A binary tree as following: v = 1 d = 3
Output:

제약:

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

아이디어:

(다음으로 이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

여러 가지 방법으로 이 문제를 확실히 해결할 수 있지만 가능하면 항상 재귀를 사용합니다. 특히 별도의 재귀 도우미 함수를 정의하지 않고 기본 함수를 간단히 재귀할 수 있는 경우에는 더욱 그렇습니다. 재귀 경로는 DFS(깊이 우선 검색) 솔루션입니다.

깊이 변수(d)를 일종의 카운트다운으로 사용할 수 있으며 대상 행에 도달할 때까지 트리를 통해 아래로 이동하면서 감소시킵니다. d에 있는 새 노드를 부모 노드에 연결해야 하므로 d = 1이 아니라 d = 2일 때 실제로 작업을 수행해야 부모 노드에 액세스할 수 있습니다.

이것은 또한 우리가 d의 원래 값이 1일 때의 스티키 에지 케이스를 처리할 수 있게 해줍니다. 원래 루트에 대한 부모가 없기 때문에 반환하기 전에 새 노드를 생성하고 여기에 루트를 연결해야 합니다. 이것은 초기 함수 호출에서만 발생할 수 있습니다. 그렇지 않으면 이후 재귀에서 d = 1에 도달하지 않습니다.

이 함수는 재귀할 때마다 노드를 반환하지만 함수가 내부적으로 호출될 때 반환 값으로 아무 작업도 수행하지 않기 때문에 원래 함수 호출에서만 실제로 의미가 있습니다.

이는 재귀를 통해 노드 참조를 전달하므로 반환 값에 관계없이 트리 개체가 수정되기 때문에 작동합니다.

구현:

코드는 네 가지 언어 모두에서 거의 동일합니다.

자바스크립트 코드:

(다음으로 이동: Problem Description || Solution Idea )

var addOneRow = function(root, v, d) {
    if (d === 1) return new TreeNode(v, root, null)
    if (d === 2) {
        root.left = new TreeNode(v, root.left, null)
        root.right = new TreeNode(v, null, root.right)
    } else {
        if (root.left) addOneRow(root.left, v, d-1)
        if (root.right) addOneRow(root.right, v, d-1)
    }
    return root
};

파이썬 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution:
    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:
        if d == 1: return TreeNode(v, root, None)
        elif d == 2:
            root.left = TreeNode(v, root.left, None)
            root.right = TreeNode(v, None, root.right)
        else:
            if root.left: self.addOneRow(root.left, v, d-1)
            if root.right: self.addOneRow(root.right, v, d-1)
        return root

자바 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
    public TreeNode addOneRow(TreeNode root, int v, int d) {
        if (d == 1) return new TreeNode(v, root, null);
        else if (d == 2) {
            root.left = new TreeNode(v, root.left, null);
            root.right = new TreeNode(v, null, root.right);
        } else {
            if (root.left != null) addOneRow(root.left, v, d-1);
            if (root.right != null) addOneRow(root.right, v, d-1);
        }
        return root;
    }
}

C++ 코드:

(다음으로 이동: Problem Description || Solution Idea )

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