235. Lowest Common Ancestor of a Binary Search Tree

LeetCode medium original: C# #csharp #leetcode #medium #search #tree #two-pointers
Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.
LeetCode Static

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

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

Ví dụ

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# lời giải

đã khớp/gố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++ lời giải

bản nháp tự động, xem lại trước khi gửi 
#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 lời giải

đã khớp/gốc 
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 lời giải

đã khớp/gốc 
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 lời giải

đã khớp/gốc 
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 lời giải

đã khớp/gốc 
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 этот узел как результат.

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm
Chưa có việc làm đang hoạt động.