669. Trim a Binary Search Tree

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

LeetCode Static

Дано корневое дерево двоичного поиска и нижняя и верхняя границы как low и high. Обрежьте дерево так, чтобы все его элементы лежали в диапазоне [low, high]. Обрезка дерева не должна изменять относительную структуру элементов, которые останутся в дереве (то есть любой потомок узла должен оставаться потомком). Можно доказать, что существует единственный ответ.

Верните корень обрезанного дерева двоичного поиска. Обратите внимание, что корень может измениться в зависимости от заданных границ.

Пример:

Input: root = [1,0,2], low = 1, high = 2

Output: [1,null,2]

C# решение

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

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class Solution {
    public TreeNode TrimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        if (root.val > high) return TrimBST(root.left, low, high);
        if (root.val < low) return TrimBST(root.right, low, high);
        root.left = TrimBST(root.left, low, high);
        root.right = TrimBST(root.right, low, high);
        return root;
    }
}

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 TreeNode TrimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        if (root.val > high) return TrimBST(root.left, low, high);
        if (root.val < low) return TrimBST(root.right, low, high);
        root.left = TrimBST(root.left, low, high);
        root.right = TrimBST(root.right, low, high);
        return root;
    }
}

Java решение

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

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

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

JavaScript решение

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

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

var trimBST = function(root, low, high) {
    if (root === null) return null
    if (root.val > high) return trimBST(root.left, low, high)
    if (root.val < low) return trimBST(root.right, low, high)
    root.left = trimBST(root.left, low, high)
    root.right = trimBST(root.right, low, high)
    return root
}

Python решение

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

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

class Solution:
    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
        if not root:
            return None
        if root.val > high:
            return self.trimBST(root.left, low, high)
        if root.val < low:
            return self.trimBST(root.right, low, high)
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root

Go решение

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

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

func trimBST(root *TreeNode, low int, high int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val > high {
        return trimBST(root.Left, low, high)
    }
    if root.Val < low {
        return trimBST(root.Right, low, high)
    }
    root.Left = trimBST(root.Left, low, high)
    root.Right = trimBST(root.Right, low, high)
    return root
}

Algorithm

Если node.val > high, то обрезанное двоичное дерево должно находиться слева от узла.

Если node.val < low, то обрезанное двоичное дерево должно находиться справа от узла.

В противном случае обрезаем обе стороны дерева.

😎

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

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

Все вакансии

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