538. Convert BST to Greater Tree

leetcode medium

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

Task

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

Напоминаем, что бинарное дерево поиска — это дерево, удовлетворяющее следующим условиям:

Левое поддерево узла содержит только узлы с ключами, меньшими ключа узла.

Правое поддерево узла содержит только узлы с ключами, большими ключа узла.

И левое, и правое поддеревья также должны быть бинарными деревьями поиска.

Пример:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]

Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

C# solution

matched/original

class Solution {
    private int sum = 0;
    public TreeNode ConvertBST(TreeNode root) {
        if (root != null) {
            ConvertBST(root.right);
            sum += root.val;
            root.val = sum;
            ConvertBST(root.left);
        }
        return root;
    }
}

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.
class Solution {
    private int sum = 0;
    public TreeNode ConvertBST(TreeNode root) {
        if (root != null) {
            ConvertBST(root.right);
            sum += root.val;
            root.val = sum;
            ConvertBST(root.left);
        }
        return root;
    }
}

Java solution

matched/original

class Solution {
    private int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root != null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}

JavaScript solution

matched/original

class Solution {
    constructor() {
        this.sum = 0;
    }

    convertBST(root) {
        if (root !== null) {
            this.convertBST(root.right);
            this.sum += root.val;
            root.val = this.sum;
            this.convertBST(root.left);
        }
        return root;
    }
}

Python solution

matched/original

class Solution:
    def __init__(self):
        self.sum = 0

    def convertBST(self, root: TreeNode) -> TreeNode:
        if root:
            self.convertBST(root.right)
            self.sum += root.val
            root.val = self.sum
            self.convertBST(root.left)
        return root

Go solution

matched/original

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

type Solution struct {
    sum int
}

func (s *Solution) ConvertBST(root *TreeNode) *TreeNode {
    if root != nil {
        s.ConvertBST(root.Right)
        s.sum += root.Val
        root.Val = s.sum
        s.ConvertBST(root.Left)
    }
    return root
}

Explanation

Algorithm

Поддерживаем глобальное состояние, чтобы каждая рекурсивная функция могла получать и изменять текущую сумму. Проверяем существование текущего узла, рекурсивно обрабатываем правое поддерево.

Посещаем текущий узел, обновляем его значение и общую сумму.

Рекурсивно обрабатываем левое поддерево.

😎