235. Lowest Common Ancestor of a Binary Search Tree

LeetCode medium original: C# #csharp #leetcode #medium #search #tree #two-pointers
El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.
LeetCode Static

given бинарное árbol поиска (BST). find Lowest common ancestor (LCA) двух заданных узлов в BST.

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

Ejemplo

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# solución

coincidente/original 
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++ solución

borrador automático, revisar antes de enviar 
#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 solución

coincidente/original 
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 solución

coincidente/original 
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 solución

coincidente/original 
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 solución

coincidente/original 
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). return этот узел как результат.

😎

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes
Todavía no hay vacantes activas.