← Static tasks

623. Add One Row to Tree

leetcode medium

#csharp#graph#leetcode#medium#queue#search#tree#two-pointers

Task

Учитывая корень бинарного дерева и два целых числа val и depth, добавьте ряд узлов со значением val на заданную глубину depth. Обратите внимание, что корневой узел находится на глубине 1. Правило добавления таково: учитывая целое число depth, для каждого ненулевого узла дерева cur на глубине depth - 1 создайте два узла дерева со значением val в качестве левого поддерева корня cur и правого поддерева корня.

Оригинальное левое поддерево cur должно быть левым поддеревом нового корня левого поддерева. Оригинальное правое поддерево cur должно быть правым поддеревом нового корня правого поддерева. Если глубина == 1, то есть глубина - 1 вообще не существует, создайте узел дерева со значением val как новый корень всего оригинального дерева, а оригинальное дерево - левое поддерево нового корня.

Пример:

Input: root = [4,2,6,3,1,5], val = 1, depth = 2

Output: [4,1,1,2,null,null,6,3,1,5]

C# solution

matched/original
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    public TreeNode AddOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            return new TreeNode(val, root);
        }
        
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        int currentDepth = 1;
        
        while (queue.Count > 0) {
            if (currentDepth == depth - 1) {
                int size = queue.Count;
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.Dequeue();
                    node.left = new TreeNode(val, node.left);
                    node.right = new TreeNode(val, null, node.right);
                }
                break;
            }
            currentDepth++;
            int size = queue.Count;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.Dequeue();
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
        }
        
        return root;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
public:
    public TreeNode AddOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            return new TreeNode(val, root);
        }
        
        queue<TreeNode> queue = new queue<TreeNode>();
        queue.Enqueue(root);
        int currentDepth = 1;
        
        while (queue.size() > 0) {
            if (currentDepth == depth - 1) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.Dequeue();
                    node.left = new TreeNode(val, node.left);
                    node.right = new TreeNode(val, null, node.right);
                }
                break;
            }
            currentDepth++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.Dequeue();
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
        }
        
        return root;
    }
}

Java solution

matched/original
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            return new TreeNode(val, root, null);
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int currentDepth = 1;
        
        while (!queue.isEmpty()) {
            if (currentDepth == depth - 1) {
                for (TreeNode node : queue) {
                    node.left = new TreeNode(val, node.left, null);
                    node.right = new TreeNode(val, null, node.right);
                }
                break;
            }
            currentDepth++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        
        return root;
    }
}

JavaScript solution

matched/original
function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
}

function addOneRow(root, val, depth) {
    if (depth === 1) {
        return new TreeNode(val, root, null);
    }
    
    const queue = [root];
    let currentDepth = 1;
    
    while (queue.length > 0) {
        if (currentDepth === depth - 1) {
            for (const node of queue) {
                node.left = new TreeNode(val, node.left, null);
                node.right = new TreeNode(val, null, node.right);
            }
            break;
        }
        currentDepth++;
        const nextQueue = [];
        for (const node of queue) {
            if (node.left !== null) {
                nextQueue.push(node.left);
            }
            if (node.right !== null) {
                nextQueue.push(node.right);
            }
        }
        queue.length = 0;
        queue.push(...nextQueue);
    }
    
    return root;
}

Python solution

matched/original
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def addOneRow(root, val, depth):
    if depth == 1:
        return TreeNode(val, left=root)
    
    queue = [root]
    current_depth = 1
    
    while queue:
        if current_depth == depth - 1:
            for node in queue:
                node.left = TreeNode(val, left=node.left)
                node.right = TreeNode(val, right=node.right)
            break
        
        current_depth += 1
        next_queue = []
        for node in queue:
            if node.left:
                next_queue.append(node.left)
            if node.right:
                next_queue.append(node.right)
        queue = next_queue
    
    return root

Go solution

matched/original
package main

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func addOneRow(root *TreeNode, val int, depth int) *TreeNode {
    if depth == 1 {
        return &TreeNode{Val: val, Left: root}
    }
    
    queue := []*TreeNode{root}
    currentDepth := 1
    
    for len(queue) > 0 {
        if currentDepth == depth-1 {
            for _, node := range queue {
                node.Left = &TreeNode{Val: val, Left: node.Left}
                node.Right = &TreeNode{Val: val, Right: node.Right}
            }
            break
        }
        currentDepth++
        nextQueue := []*TreeNode{}
        for _, node := range queue {
            if node.Left != nil {
                nextQueue = append(nextQueue, node.Left)
            }
            if node.Right != nil {
                nextQueue = append(nextQueue, node.Right)
            }
        }
        queue = nextQueue
    }
    
    return root
}

Explanation

Algorithm

Если depth равна 1, создайте новый корень со значением val и сделайте текущий корень левым поддеревом нового корня.

Используйте обход в ширину (BFS) для поиска всех узлов на глубине depth - 1.

Для каждого узла на глубине depth - 1, вставьте новые узлы со значением val в качестве левого и правого поддеревьев, сохраняя исходные поддеревья.

😎