776. Split BST

leetcode medium

#array#csharp#leetcode#medium#recursion#search#tree#two-pointers

Task

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

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

Верните массив из двух корней двух поддеревьев в порядке.

Пример:

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]}
    }
}

Explanation

Algorithm

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

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

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

😎