426. Convert Binary Search Tree to Sorted Doubly Linked List

leetcode medium

#csharp#leetcode#linked-list#medium#recursion#search#sort#tree#two-pointers

Task

Преобразуйте двоичное дерево поиска в отсортированный кольцевой двусвязный список на месте.

Вы можете считать, что указатели "влево" и "вправо" аналогичны указателям на предшественника и последователя в двусвязном списке. Для кольцевого двусвязного списка предшественник первого элемента является последним элементом, а последователь последнего элемента является первым элементом.

Мы хотим выполнить преобразование на месте. После преобразования левый указатель узла дерева должен указывать на его предшественника, а правый указатель должен указывать на его последователя. Вы должны вернуть указатель на самый маленький элемент списка.

Пример:

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

Output: [1,2,3,4,5]

Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

C# solution

matched/original

public class Node {
    public int val;
    public Node left;
    public Node right;
    public Node() {}
    public Node(int _val) {
        val = _val;
        left = null;
        right = null;
    }
    public Node(int _val, Node _left, Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}
public class Solution {
    private Node first = null;
    private Node last = null;
    private void Helper(Node node) {
        if (node != null) {
            Helper(node.left);
            if (last != null) {
                last.right = node;
                node.left = last;
            } else {
                first = node;
            }
            last = node;
            Helper(node.right);
        }
    }
    public Node TreeToDoublyList(Node root) {
        if (root == null) return null;
        Helper(root);
        last.right = first;
        first.left = last;
        return first;
    }
}

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 Node {
    public int val;
    public Node left;
    public Node right;
    public Node() {}
    public Node(int _val) {
        val = _val;
        left = null;
        right = null;
    }
    public Node(int _val, Node _left, Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}
class Solution {
public:
    private Node first = null;
    private Node last = null;
    private void Helper(Node node) {
        if (node != null) {
            Helper(node.left);
            if (last != null) {
                last.right = node;
                node.left = last;
            } else {
                first = node;
            }
            last = node;
            Helper(node.right);
        }
    }
    public Node TreeToDoublyList(Node root) {
        if (root == null) return null;
        Helper(root);
        last.right = first;
        first.left = last;
        return first;
    }
}

Java solution

matched/original

class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}

class Solution {
    private Node first = null;
    private Node last = null;

    public void helper(Node node) {
        if (node != null) {
            helper(node.left);

            if (last != null) {
                last.right = node;
                node.left = last;
            } else {
                first = node;
            }
            last = node;

            helper(node.right);
        }
    }

    public Node treeToDoublyList(Node root) {
        if (root == null) return null;

        helper(root);

        last.right = first;
        first.left = last;
        return first;
    }
}

JavaScript solution

matched/original

class Node {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    constructor() {
        this.first = null;
        this.last = null;
    }

    helper(node) {
        if (node !== null) {
            this.helper(node.left);

            if (this.last !== null) {
                this.last.right = node;
                node.left = this.last;
            } else {
                this.first = node;
            }
            this.last = node;

            this.helper(node.right);
        }
    }

    treeToDoublyList(root) {
        if (root === null) return null;

        this.helper(root);

        this.last.right = this.first;
        this.first.left = this.last;
        return this.first;
    }
}

Go solution

matched/original

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

func helper(node *Node, first **Node, last **Node) {
    if node != nil {
        helper(node.Left, first, last)

        if *last != nil {
            (*last).Right = node
            node.Left = *last
        } else {
            *first = node
        }
        *last = node

        helper(node.Right, first, last)
    }
}

func treeToDoublyList(root *Node) *Node {
    if root == nil {
        return nil
    }

    var first, last *Node
    helper(root, &first, &last)

    last.Right = first
    first.Left = last
    return first
}

Explanation

Algorithm

Инициализируйте первые и последние узлы как null.

Вызовите стандартную вспомогательную рекурсивную функцию helper(root):

Если узел не равен null:

Вызовите рекурсию для левого поддерева helper(node.left).

Если последний узел не равен null, свяжите последний узел и текущий узел.

Иначе инициализируйте первый узел.

Пометьте текущий узел как последний: last = node.

Вызовите рекурсию для правого поддерева helper(node.right).

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

😎