285. Inorder Successor in BST

leetcode medium

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

Task

Дан корень бинарного дерева поиска и узел p в нем. Верните преемника этого узла в порядке возрастания в бинарном дереве поиска (BST). Если у данного узла нет преемника в порядке возрастания в дереве, верните null.

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

Пример:

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# solution

matched/original

public 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++ 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 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 solution

matched/original

class 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 solution

matched/original

class 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 solution

matched/original

class 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 solution

matched/original

type 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)
}

Explanation

Algorithm

Определение переменных класса:

Определите две переменные класса: previous и inorderSuccessorNode. Переменная previous будет использоваться при обработке второго случая, а inorderSuccessorNode будет содержать результат, который нужно вернуть.

Обработка двух случаев:

В функции inorderSuccessor сначала проверьте, какой из двух случаев нужно обработать, проверяя наличие правого дочернего элемента.

Правый дочерний элемент существует:

- присвойте правый дочерний элемент узлу leftmost и итерируйтесь, пока не достигнете узла (leftmost), у которого нет левого дочернего элемента. Итерируйте, присваивая leftmost = leftmost.left, пока не получите левый узел в поддереве.

Правый дочерний элемент не существует:

- определите функцию inorderCase2 и передайте ей узел и узел p.

- выполните простой обход в порядке возрастания: сначала рекурсируйте на левый дочерний элемент узла.

- когда рекурсия вернется, проверьте, равна ли переменная класса previous узлу p. Если это так, значит p является предшественником узла, или, другими словами, узел является преемником узла p. Назначьте inorderSuccessorNode узлу и вернитесь из функции.

- наконец, верните inorderSuccessorNode как результат.

Итерация и обновление:

В функции inorderCase2 обновляйте previous текущим узлом и продолжайте рекурсировать на правый дочерний элемент.

😎