617. Merge Two Binary Trees

LeetCode medium оригинал: C# #csharp #leetcode #medium #recursion #tree #two-pointers

LeetCode Static

Вам даны два бинарных дерева root1 и root2. Представьте, что при наложении одного из них на другое некоторые узлы двух деревьев перекрываются, а другие - нет. Вам нужно объединить эти два дерева в новое бинарное дерево. Правило слияния таково: если два узла пересекаются, то в качестве нового значения объединенного узла используется сумма значений узлов. В противном случае в качестве узла нового дерева будет использоваться узел NOT null. Возвращается объединенное дерево. Примечание: Процесс объединения должен начинаться с корневых узлов обоих деревьев.

Пример:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]

Output: [3,4,5,5,4,null,7]

C# решение

сопоставлено/оригинал

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 MergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;
        
        TreeNode mergedNode = new TreeNode(root1.val + root2.val);
        mergedNode.left = MergeTrees(root1.left, root2.left);
        mergedNode.right = MergeTrees(root1.right, root2.right);
        
        return mergedNode;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#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 MergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;
        
        TreeNode mergedNode = new TreeNode(root1.val + root2.val);
        mergedNode.left = MergeTrees(root1.left, root2.left);
        mergedNode.right = MergeTrees(root1.right, root2.right);
        
        return mergedNode;
    }
}

Java решение

сопоставлено/оригинал

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        
        TreeNode mergedNode = new TreeNode(root1.val + root2.val);
        mergedNode.left = mergeTrees(root1.left, root2.left);
        mergedNode.right = mergeTrees(root1.right, root2.right);
        
        return mergedNode;
    }
}

JavaScript решение

сопоставлено/оригинал

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

function mergeTrees(root1, root2) {
    if (!root1) return root2;
    if (!root2) return root1;
    
    const mergedNode = new TreeNode(root1.val + root2.val);
    mergedNode.left = mergeTrees(root1.left, root2.left);
    mergedNode.right = mergeTrees(root1.right, root2.right);
    
    return mergedNode;
}

Python решение

сопоставлено/оригинал

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

def mergeTrees(root1, root2):
    if not root1:
        return root2
    if not root2:
        return root1
    
    mergedNode = TreeNode(root1.val + root2.val)
    mergedNode.left = mergeTrees(root1.left, root2.left)
    mergedNode.right = mergeTrees(root1.right, root2.right)
    
    return mergedNode

Go решение

сопоставлено/оригинал

package main

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

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    }
    if root2 == nil {
        return root1
    }
    
    mergedNode := &TreeNode{Val: root1.Val + root2.Val}
    mergedNode.Left = mergeTrees(root1.Left, root2.Left)
    mergedNode.Right = mergeTrees(root1.Right, root2.Right)
    
    return mergedNode
}

Algorithm

Если один из узлов пуст (null), возвращаем другой узел. Если оба узла пустые, возвращаем null.

Если оба узла не пустые, создаем новый узел, значение которого равно сумме значений двух узлов. Рекурсивно объединяем левые и правые поддеревья.

Возвращаем новый узел, который является корнем объединенного дерева.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.