285. Inorder Successor in BST
Дан корень бинарного дерева поиска и узел p в нем. return преемника этого узла в порядке возрастания в бинарном дереве поиска (BST). Если у данного узла нет преемника в порядке возрастания в дереве, return null.
Преемник узла p — это узел с наименьшим ключом, который больше p.val.
Beispiel:
Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.
C# Lösung
zugeordnet/originalpublic class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private TreeNode previous = null;
private TreeNode inorderSuccessorNode = null;
public TreeNode InorderSuccessor(TreeNode root, TreeNode p) {
if (p.right != null) {
TreeNode leftmost = p.right;
while (leftmost.left != null) {
leftmost = leftmost.left;
}
inorderSuccessorNode = leftmost;
} else {
InorderCase2(root, p);
}
return inorderSuccessorNode;
}
private void InorderCase2(TreeNode node, TreeNode p) {
if (node == null) {
return;
}
InorderCase2(node.left, p);
if (previous == p && inorderSuccessorNode == null) {
inorderSuccessorNode = node;
return;
}
previous = node;
InorderCase2(node.right, p);
}
}C++ Lösung
Auto-Entwurf, vor dem Einreichen prüfen#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:
private TreeNode previous = null;
private TreeNode inorderSuccessorNode = null;
public TreeNode InorderSuccessor(TreeNode root, TreeNode p) {
if (p.right != null) {
TreeNode leftmost = p.right;
while (leftmost.left != null) {
leftmost = leftmost.left;
}
inorderSuccessorNode = leftmost;
} else {
InorderCase2(root, p);
}
return inorderSuccessorNode;
}
private void InorderCase2(TreeNode node, TreeNode p) {
if (node == null) {
return;
}
InorderCase2(node.left, p);
if (previous == p && inorderSuccessorNode == null) {
inorderSuccessorNode = node;
return;
}
previous = node;
InorderCase2(node.right, p);
}
}Java Lösung
zugeordnet/originalclass Solution {
private TreeNode previous;
private TreeNode inorderSuccessorNode;
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if (p.right != null) {
TreeNode leftmost = p.right;
while (leftmost.left != null) {
leftmost = leftmost.left;
}
this.inorderSuccessorNode = leftmost;
} else {
this.inorderCase2(root, p);
}
return this.inorderSuccessorNode;
}
private void inorderCase2(TreeNode node, TreeNode p) {
if (node == null) {
return;
}
this.inorderCase2(node.left, p);
if (this.previous == p && this.inorderSuccessorNode == null) {
this.inorderSuccessorNode = node;
return;
}
this.previous = node;
this.inorderCase2(node.right, p);
}
}JavaScript Lösung
zugeordnet/originalclass TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
class Solution {
constructor() {
this.previous = null;
this.inorderSuccessorNode = null;
}
inorderSuccessor(root, p) {
if (p.right !== null) {
let leftmost = p.right;
while (leftmost.left !== null) {
leftmost = leftmost.left;
}
this.inorderSuccessorNode = leftmost;
} else {
this.inorderCase2(root, p);
}
return this.inorderSuccessorNode;
}
inorderCase2(node, p) {
if (node === null) {
return;
}
this.inorderCase2(node.left, p);
if (this.previous === p && this.inorderSuccessorNode === null) {
this.inorderSuccessorNode = node;
return;
}
this.previous = node;
this.inorderCase2(node.right, p);
}
}Python Lösung
zugeordnet/originalclass TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def __init__(self):
self.previous = None
self.inorderSuccessorNode = None
def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
if p.right:
leftmost = p.right
while leftmost.left:
leftmost = leftmost.left
self.inorderSuccessorNode = leftmost
else:
self.inorderCase2(root, p)
return self.inorderSuccessorNode
def inorderCase2(self, node: TreeNode, p: TreeNode):
if not node:
return
self.inorderCase2(node.left, p)
if self.previous == p and self.inorderSuccessorNode is None:
self.inorderSuccessorNode = node
return
self.previous = node
self.inorderCase2(node.right, p)Go Lösung
zugeordnet/originaltype TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
type Solution struct {
previous *TreeNode
inorderSuccessorNode *TreeNode
}
func (s *Solution) inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
if p.Right != nil {
leftmost := p.Right
for leftmost.Left != nil {
leftmost = leftmost.Left
}
s.inorderSuccessorNode = leftmost
} else {
s.inorderCase2(root, p)
}
return s.inorderSuccessorNode
}
func (s *Solution) inorderCase2(node *TreeNode, p *TreeNode) {
if node == nil {
return
}
s.inorderCase2(node.Left, p)
if s.previous == p && s.inorderSuccessorNode == nil {
s.inorderSuccessorNode = node
return
}
s.previous = node
s.inorderCase2(node.Right, p)
}Algorithm
Definition переменных класса:
Определите две переменные класса: previous и inorderSuccessorNode. Переменная previous будет использоваться при обработке второго случая, а inorderSuccessorNode будет содержать результат, который нужно вернуть.
Обработка двух случаев:
В функции inorderSuccessor сначала проверьте, какой из двух случаев нужно обработать, проверяя наличие правого дочернего elementа.
Правый дочерний element существует:
- присвойте правый дочерний element узлу leftmost и итерируйтесь, пока не достигнете узла (leftmost), у которого нет левого дочернего elementа. Итерируйте, присваивая leftmost = leftmost.left, пока не получите левый узел в поддереве.
Правый дочерний element не существует:
- определите функцию inorderCase2 и передайте ей узел и узел p.
- выполните простой обход в порядке возрастания: сначала рекурсируйте на левый дочерний element узла.
- когда рекурсия вернется, проверьте, равна ли переменная класса previous узлу p. Если это так, значит p является предшественником узла, или, другими словами, узел является преемником узла p. Назначьте inorderSuccessorNode узлу и returnсь из функции.
- наконец, return inorderSuccessorNode как результат.
Итерация и обновление:
В функции inorderCase2 обновляйте previous текущим узлом и продолжайте рекурсировать на правый дочерний element.
😎
Stellen zu dieser Aufgabe
aktive Stellen with overlapping task tags are angezeigt.