776. Split BST

LeetCode medium original: C# #array #csharp #leetcode #medium #recursion #search #tree #two-pointers

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

Дан корень бинарного дерева поиска (BST) и integer target, разделите tree на два поддерева, где первое подtree содержит узлы, которые меньше или равны значению target, а второе подtree содержит узлы, которые больше значения target. Не обязательно, чтобы tree содержало узел со значением target.

Кроме того, большая часть структуры исходного дерева должна сохраниться. Формально, для любого потомка c с родителем p в исходном дереве, если они оба находятся в одном поддереве после разделения, то узел c все еще должен иметь родителя p.

return array из двух корней двух поддеревьев в порядке.

Example:

Input: root = [4,2,6,1,3,5,7], target = 2

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

C# solution

matched/original

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class Solution {
    public TreeNode[] SplitBST(TreeNode root, int target) {
        if (root == null) {
            return new TreeNode[]{null, null};
        }
        if (root.val > target) {
            TreeNode[] left = SplitBST(root.left, target);
            root.left = left[1];
            return new TreeNode[]{left[0], root};
        } else {
            TreeNode[] right = SplitBST(root.right, target);
            root.right = right[0];
            return new TreeNode[]{root, right[1]};
        }
    }
}

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 x) { val = x; }
}
class Solution {
public:
    public TreeNode[] SplitBST(TreeNode root, int target) {
        if (root == null) {
            return new TreeNode[]{null, null};
        }
        if (root.val > target) {
            TreeNode[] left = SplitBST(root.left, target);
            root.left = left[1];
            return new TreeNode[]{left[0], root};
        } else {
            TreeNode[] right = SplitBST(root.right, target);
            root.right = right[0];
            return new TreeNode[]{root, right[1]};
        }
    }
}

Java solution

matched/original

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

class Solution {
    public TreeNode[] splitBST(TreeNode root, int target) {
        if (root == null) {
            return new TreeNode[]{null, null};
        }

        if (root.val > target) {
            TreeNode[] left = splitBST(root.left, target);
            root.left = left[1];
            return new TreeNode[]{left[0], root};
        } else {
            TreeNode[] right = splitBST(root.right, target);
            root.right = right[0];
            return new TreeNode[]{root, right[1]};
        }
    }
}

JavaScript solution

matched/original

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var splitBST = function(root, target) {
    if (!root) {
        return [null, null];
    }

    if (root.val > target) {
        let left = splitBST(root.left, target);
        root.left = left[1];
        return [left[0], root];
    } else {
        let right = splitBST(root.right, target);
        root.right = right[0];
        return [root, right[1]];
    }
};

Python solution

matched/original

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

class Solution:
    def splitBST(self, root: TreeNode, target: int) -> List[TreeNode]:
        if not root:
            return [None, None]
        
        if root.val > target:
            left = self.splitBST(root.left, target)
            root.left = left[1]
            return [left[0], root]
        else:
            right = self.splitBST(root.right, target)
            root.right = right[0]
            return [root, right[1]]

Go solution

matched/original

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

func splitBST(root *TreeNode, target int) []*TreeNode {
    if root == nil {
        return []*TreeNode{nil, nil}
    }

    if root.Val > target {
        left := splitBST(root.Left, target)
        root.Left = left[1]
        return []*TreeNode{left[0], root}
    } else {
        right := splitBST(root.Right, target)
        root.Right = right[0]
        return []*TreeNode{root, right[1]}
    }
}

Algorithm

Базовый случай: Если корень равен null, return array, содержащий два указателя null. Это необходимо для обработки случая, когда tree пустое.

Проверьте, больше ли значение корня целевого значения. Если да, рекурсивно разделите левое подtree, вызвав splitBST(root->left, target). Прикрепите правую часть разделенного к левому поддереву корня. return array, содержащий левую часть разделенного и текущий корень.

Если значение корня меньше или равно целевому значению, рекурсивно разделите правое подtree, вызвав splitBST(root->right, target). Прикрепите левую часть разделенного к правому поддереву корня. return array, содержащий левую часть разделенного и текущий корень.

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.