99. Recover Binary Search Tree

leetcode medium

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

Task

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

Пример:

Input: root = [1,3,null,null,2]

Output: [3,1,null,null,2]

Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

C# solution

matched/original

public class Solution {
    private void Inorder(TreeNode root, List<int> nums) {
        if (root == null)
            return;
        Inorder(root.left, nums);
        nums.Add(root.val);
        Inorder(root.right, nums);
    }
    private int[] FindTwoSwapped(List<int> nums) {
        int n = nums.Count;
        int x = -1, y = -1;
        bool swappedFirstOccurrence = false;
        for (int i = 0; i < n - 1; ++i) {
            if (nums[i + 1] < nums[i]) {
                y = nums[i + 1];
                if (!swappedFirstOccurrence) {
                    x = nums[i];
                    swappedFirstOccurrence = true;
                } else {
                    break;
                }
            }
        }
        return new int[] { x, y };
    }
    private void Recover(TreeNode r, int count, int x, int y) {
        if (r != null) {
            if (r.val == x || r.val == y) {
                r.val = r.val == x ? y : x;
                if (--count == 0)
                    return;
            }
            Recover(r.left, count, x, y);
            Recover(r.right, count, x, y);
        }
    }
    public void RecoverTree(TreeNode root) {
        List<int> nums = new List<int>();
        Inorder(root, nums);
        int[] swapped = FindTwoSwapped(nums);
        Recover(root, 2, swapped[0], swapped[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.
class Solution {
public:
    private void Inorder(TreeNode root, List<int> nums) {
        if (root == null)
            return;
        Inorder(root.left, nums);
        nums.push_back(root.val);
        Inorder(root.right, nums);
    }
    private vector<int>& FindTwoSwapped(List<int> nums) {
        int n = nums.size();
        int x = -1, y = -1;
        bool swappedFirstOccurrence = false;
        for (int i = 0; i < n - 1; ++i) {
            if (nums[i + 1] < nums[i]) {
                y = nums[i + 1];
                if (!swappedFirstOccurrence) {
                    x = nums[i];
                    swappedFirstOccurrence = true;
                } else {
                    break;
                }
            }
        }
        return new int[] { x, y };
    }
    private void Recover(TreeNode r, int count, int x, int y) {
        if (r != null) {
            if (r.val == x || r.val == y) {
                r.val = r.val == x ? y : x;
                if (--count == 0)
                    return;
            }
            Recover(r.left, count, x, y);
            Recover(r.right, count, x, y);
        }
    }
    public void RecoverTree(TreeNode root) {
        List<int> nums = new List<int>();
        Inorder(root, nums);
        vector<int>& swapped = FindTwoSwapped(nums);
        Recover(root, 2, swapped[0], swapped[1]);
    }
}

Java solution

matched/original

class Solution {
    public void inorder(TreeNode root, List<Integer> nums) {
        if (root == null) return;
        inorder(root.left, nums);
        nums.add(root.val);
        inorder(root.right, nums);
    }

    public int[] findTwoSwapped(List<Integer> nums) {
        int n = nums.size();
        int x = -1, y = -1;
        boolean swapped_first_occurrence = false;

        for (int i = 0; i < n - 1; ++i) {
            if (nums.get(i + 1) < nums.get(i)) {
                y = nums.get(i + 1);
                if (!swapped_first_occurrence) {
                    x = nums.get(i);
                    swapped_first_occurrence = true;
                } else {
                    break;
                }
            }
        }
        return new int[] { x, y };
    }

    public void recover(TreeNode r, int count, int x, int y) {
        if (r != null) {
            if (r.val == x || r.val == y) {
                r.val = r.val == x ? y : x;
                if (--count == 0) return;
            }
            recover(r.left, count, x, y);
            recover(r.right, count, x, y);
        }
    }

    public void recoverTree(TreeNode root) {
        List<Integer> nums = new ArrayList();
        inorder(root, nums);
        int[] swapped = findTwoSwapped(nums);
        recover(root, 2, swapped[0], swapped[1]);
    }
}

JavaScript solution

matched/original

var inorder = function (root, nums) {
    if (!root) return;
    inorder(root.left, nums);
    nums.push(root.val);
    inorder(root.right, nums);
};

var findTwoSwapped = function (nums) {
    let n = nums.length;
    let x = -1,
        y = -1;
    let swappedFirstOccurrence = false;

    for (let i = 0; i < n - 1; ++i) {
        if (nums[i + 1] < nums[i]) {
            y = nums[i + 1];
            if (!swappedFirstOccurrence) {
                x = nums[i];
                swappedFirstOccurrence = true;
            } else {
                break;
            }
        }
    }
    return [x, y];
};

var recover = function (r, count, x, y) {
    if (r) {
        if (r.val === x || r.val === y) {
            r.val = r.val === x ? y : x;
            if (--count === 0) return;
        }
        recover(r.left, count, x, y);
        recover(r.right, count, x, y);
    }
};

var recoverTree = function (root) {
    let nums = [];
    inorder(root, nums);
    let swapped = findTwoSwapped(nums);
    recover(root, 2, swapped[0], swapped[1]);
};

Python solution

matched/original

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        def inorder(r: TreeNode) -> List[int]:
            return inorder(r.left) + [r.val] + inorder(r.right) if r else []

        def find_two_swapped(nums: List[int]) -> (int, int):
            n = len(nums)
            x = y = (
                None  
            )

            for i in range(n - 1):
                if nums[i + 1] < nums[i]:
                    y = nums[i + 1]
                    if x is None:
                        x = nums[i]
                    else:
                        break
            return x, y

        def recover(r: TreeNode, count: int) -> None:
            if r:
                if r.val == x or r.val == y:
                    r.val = y if r.val == x else x
                    count -= 1
                    if count == 0:
                        return
                recover(r.left, count)
                recover(r.right, count)

        nums = inorder(root)
        x, y = find_two_swapped(nums)
        recover(root, 2)

Go solution

matched/original

func recoverTree(root *TreeNode) {
    nums := inorder(root)
    x, y := findTwoSwapped(nums)
    count := 2
    recover(root, &count, x, y)
}

func inorder(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    nums := inorder(root.Left)
    nums = append(nums, root.Val)
    nums = append(nums, inorder(root.Right)...)
    return nums
}

func findTwoSwapped(nums []int) (int, int) {
    n := len(nums)
    x, y := -1, -1
    swapped_first_occurrence := false
    for i := 0; i < n-1; i++ {
        if nums[i+1] < nums[i] {
            y = nums[i+1]
            if !swapped_first_occurrence {
                x = nums[i]
                swapped_first_occurrence = true
            } else {
                break
            }
        }
    }
    return x, y
}

func recover(root *TreeNode, count *int, x int, y int) {
    if root != nil {
        if root.Val == x || root.Val == y {
            if root.Val == x {
                root.Val = y
            } else {
                root.Val = x
            }
            *count -= 1
            if *count == 0 {
                return
            }
        }
        recover(root.Left, count, x, y)
        recover(root.Right, count, x, y)
    }
}

Explanation

Algorithm

1️⃣

Создайте симметричный обход дерева. Это должен быть почти отсортированный список, в котором поменяны местами только два элемента.

2️⃣

Определите два поменянных местами элемента x и y в почти отсортированном массиве за линейное время.

3️⃣

Повторно пройдите по дереву. Измените значение x на y и значение y на x.

😎