510. Inorder Successor in BST II

LeetCode medium оригинал: C# #csharp #leetcode #medium #search #tree #two-pointers

LeetCode Static

Дан узел в двоичном дереве поиска, верните его последующего (in-order successor) в этом дереве. Если у узла нет последующего, верните null.

Последующий узла — это узел с наименьшим ключом, большим, чем node.val.

Вы будете иметь прямой доступ к узлу, но не к корню дерева. Каждый узел будет иметь ссылку на своего родителя. Ниже приведено определение для Node:

class Node {

public int val;

public Node left;

public Node right;

public Node parent;

}

Пример:

Input: tree = [5,3,6,2,4,null,null,1], node = 6

Output: null

Explanation: There is no in-order successor of the current node, so the answer is null.

C# решение

сопоставлено/оригинал

public class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}
public class Solution {
    public Node InorderSuccessor(Node x) {
        if (x.right != null) {
            x = x.right;
            while (x.left != null) {
                x = x.left;
            }
            return x;
        }
        while (x.parent != null && x == x.parent.right) {
            x = x.parent;
        }
        return x.parent;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#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 parent;
}
class Solution {
public:
    public Node InorderSuccessor(Node x) {
        if (x.right != null) {
            x = x.right;
            while (x.left != null) {
                x = x.left;
            }
            return x;
        }
        while (x.parent != null && x == x.parent.right) {
            x = x.parent;
        }
        return x.parent;
    }
}

Java решение

сопоставлено/оригинал

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

class Solution {
  public Node inorderSuccessor(Node x) {
    if (x.right != null) {
      x = x.right;
      while (x.left != null) x = x.left;
      return x;
    }

    while (x.parent != null && x == x.parent.right) x = x.parent;
    return x.parent;
  }
}

JavaScript решение

сопоставлено/оригинал

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

var inorderSuccessor = function(x) {
    if (x.right) {
        x = x.right;
        while (x.left) {
            x = x.left;
        }
        return x;
    }

    while (x.parent && x === x.parent.right) {
        x = x.parent;
    }
    return x.parent;
};

Python решение

сопоставлено/оригинал

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

class Solution:
    def inorderSuccessor(self, x: 'Node') -> 'Node':
        if x.right:
            x = x.right
            while x.left:
                x = x.left
            return x

        while x.parent and x == x.parent.right:
            x = x.parent
        return x.parent

Go решение

сопоставлено/оригинал

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

func inorderSuccessor(x *Node) *Node {
    if x.Right != nil {
        x = x.Right
        for x.Left != nil {
            x = x.Left
        }
        return x
    }

    for x.Parent != nil && x == x.Parent.Right {
        x = x.Parent
    }
    return x.Parent
}

Algorithm

Проверка правого поддерева

Если у узла есть правый потомок, перейдите к правому узлу, затем спускайтесь влево до самого нижнего узла. Этот узел будет следующим узлом в порядке in-order.

Поиск предка

Если у узла нет правого потомка, поднимайтесь по дереву до тех пор, пока узел не станет левым потомком своего родителя. Родитель этого узла будет следующим узлом в порядке in-order.

Возвращение результата

Верните найденный узел или null, если следующий узел не найден.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.