1305. All Elements in Two Binary Search Trees

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

LeetCode Static

Даны два бинарных дерева поиска root1 и root2. Вернуть список, содержащий все целые числа из обоих деревьев, отсортированные в порядке возрастания.

Пример:

Input: root1 = [2,1,4], root2 = [1,0,3]

Output: [0,1,1,2,3,4]

C# решение

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

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class Solution {
    public IList<int> GetAllElements(TreeNode root1, TreeNode root2) {
        var stack1 = new Stack<TreeNode>();
        var stack2 = new Stack<TreeNode>();
        var output = new List<int>();
        while (root1 != null || root2 != null || stack1.Count > 0 || stack2.Count > 0) {
            while (root1 != null) {
                stack1.Push(root1);
                root1 = root1.left;
            }
            while (root2 != null) {
                stack2.Push(root2);
                root2 = root2.left;
            }
            if (stack2.Count == 0 || (stack1.Count > 0 && stack1.Peek().val <= stack2.Peek().val)) {
                root1 = stack1.Pop();
                output.Add(root1.val);
                root1 = root1.right;
            } else {
                root2 = stack2.Pop();
                output.Add(root2.val);
                root2 = root2.right;
            }
        }
        return output;
    }
}

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 x) { val = x; }
}
class Solution {
public:
    public vector<int> GetAllElements(TreeNode root1, TreeNode root2) {
        var stack1 = new stack<TreeNode>();
        var stack2 = new stack<TreeNode>();
        var output = new List<int>();
        while (root1 != null || root2 != null || stack1.size() > 0 || stack2.size() > 0) {
            while (root1 != null) {
                stack1.push(root1);
                root1 = root1.left;
            }
            while (root2 != null) {
                stack2.push(root2);
                root2 = root2.left;
            }
            if (stack2.size() == 0 || (stack1.size() > 0 && stack1.Peek().val <= stack2.Peek().val)) {
                root1 = stack1.pop();
                output.push_back(root1.val);
                root1 = root1.right;
            } else {
                root2 = stack2.pop();
                output.push_back(root2.val);
                root2 = root2.right;
            }
        }
        return output;
    }
}

Java решение

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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        ArrayDeque<TreeNode> stack1 = new ArrayDeque<>(), stack2 = new ArrayDeque<>();
        List<Integer> output = new ArrayList<>();

        while (root1 != null || root2 != null || !stack1.isEmpty() || !stack2.isEmpty()) {
            while (root1 != null) {
                stack1.push(root1);
                root1 = root1.left;
            }
            while (root2 != null) {
                stack2.push(root2);
                root2 = root2.left;
            }
            if (stack2.isEmpty() || (!stack1.isEmpty() && stack1.peek().val <= stack2.peek().val)) {
                root1 = stack1.pop();
                output.add(root1.val);
                root1 = root1.right;
            } else {
                root2 = stack2.pop();
                output.add(root2.val);
                root2 = root2.right;
            }
        }
        return output;
    }
}

JavaScript решение

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

package main
var getAllElements = function(root1, root2) {
    const stack1 = [], stack2 = [];
    const output = [];

    while (root1 || root2 || stack1.length || stack2.length) {
        while (root1) {
            stack1.push(root1);
            root1 = root1.left;
        }
        while (root2) {
            stack2.push(root2);
            root2 = root2.left;
        }
        if (!stack2.length || (stack1.length && stack1[stack1.length - 1].val <= stack2[stack2.length - 1].val)) {
            root1 = stack1.pop();
            output.push(root1.val);
            root1 = root1.right

Go решение

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

package main

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

func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
    stack1, stack2 := []*TreeNode{}, []*TreeNode{}
    output := []int{}

    for root1 != nil || root2 != nil || len(stack1) > 0 || len(stack2) > 0 {
        for root1 != nil {
            stack1 = append(stack1, root1)
            root1 = root1.Left
        }
        for root2 != nil {
            stack2 = append(stack2, root2)
            root2 = root2.Left
        }
        if len(stack2) == 0 || (len(stack1) > 0 && stack1[len(stack1)-1].Val <= stack2[len(stack2)-1].Val) {
            root1 = stack1[len(stack1)-1]
            stack1 = stack1[:len(stack1)-1]
            output = append(output, root1.Val)
            root1 = root1.Right
        } else {
            root2 = stack2[len(stack2)-1]
            stack2 = stack2[:len(stack2)-1]
            output = append(output, root2.Val)
            root2 = root2.Right
        }
    }
    return output
}

Algorithm

Выполните итеративный обход в порядке возрастания обоих деревьев параллельно.

На каждом шаге добавляйте наименьшее доступное значение в выходной список.

Верните выходной список.

😎

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

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

Все вакансии

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