235. Lowest Common Ancestor of a Binary Search Tree

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

Дано бинарное дерево поиска (BST). Найдите наименьший общий предок (LCA) двух заданных узлов в BST.

Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)."

Пример

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

Output: 6

Explanation: The LCA of nodes 2 and 8 is 6.

C# решение

сопоставлено/оригинал 
public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int parentVal = root.val;
        int pVal = p.val;
        int qVal = q.val;
        if (pVal > parentVal && qVal > parentVal) {
            return LowestCommonAncestor(root.right, p, q);
        } else if (pVal < parentVal && qVal < parentVal) {
            return LowestCommonAncestor(root.left, p, q);
        } else {
            return root;
        }
    }
}

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.
class Solution {
public:
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int parentVal = root.val;
        int pVal = p.val;
        int qVal = q.val;
        if (pVal > parentVal && qVal > parentVal) {
            return LowestCommonAncestor(root.right, p, q);
        } else if (pVal < parentVal && qVal < parentVal) {
            return LowestCommonAncestor(root.left, p, q);
        } else {
            return root;
        }
    }
}

Java решение

сопоставлено/оригинал 
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int parentVal = root.val;
        int pVal = p.val;
        int qVal = q.val;

        if (pVal > parentVal && qVal > parentVal) {
            return lowestCommonAncestor(root.right, p, q);
        } else if (pVal < parentVal && qVal < parentVal) {
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return root;
        }
    }
}

JavaScript решение

сопоставлено/оригинал 
class Solution {
    lowestCommonAncestor(root, p, q) {
        const parentVal = root.val
        const pVal = p.val
        const qVal = q.val

        if (pVal > parentVal && qVal > parentVal) {
            return this.lowestCommonAncestor(root.right, p, q)
        } else if (pVal < parentVal && qVal < parentVal) {
            return this.lowestCommonAncestor(root.left, p, q)
        } else {
            return root
        }
    }
}

Python решение

сопоставлено/оригинал 
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        parentVal = root.val
        pVal = p.val
        qVal = q.val

        if pVal > parentVal and qVal > parentVal:
            return self.lowestCommonAncestor(root.right, p, q)
        elif pVal < parentVal and qVal < parentVal:
            return self.lowestCommonAncestor(root.left, p, q)
        else:
            return root

Go решение

сопоставлено/оригинал 
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    parentVal := root.Val
    pVal := p.Val
    qVal := q.Val

    if pVal > parentVal && qVal > parentVal {
        return lowestCommonAncestor(root.Right, p, q)
    } else if pVal < parentVal && qVal < parentVal {
        return lowestCommonAncestor(root.Left, p, q)
    } else {
        return root
    }
}

Algorithm

Начало обхода дерева с корня: Начните обход дерева с корневого узла. Проверьте, находятся ли узлы p и q в правом или левом поддереве текущего узла.

Продолжение поиска в поддереве: Если оба узла p и q находятся в правом поддереве текущего узла, продолжайте поиск в правом поддереве, начиная с шага 1. Если оба узла p и q находятся в левом поддереве текущего узла, продолжайте поиск в левом поддереве, начиная с шага 1.

Нахождение LCA: Если узлы p и q находятся в разных поддеревьях относительно текущего узла или один из узлов равен текущему узлу, то текущий узел является наименьшим общим предком (LCA). Верните этот узел как результат.

😎

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

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

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