gpt4 book ai didi

algorithm - 在给定二叉树中的两个值的情况下查找最不常见的祖先

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:09:06 26 4
gpt4 key购买 nike

<分区>

我在编程面试中遇到了这个问题。请随意考虑如何回答。

给定一个二叉树(不是二叉搜索树)的根节点,其中每个节点都包含一个整数值,并且没有值出现两次。您还获得了两个值 val1val2(它们可能在也可能不在树中。)如果两者都在树中,则返回最小的节点包含这两个值的两个节点的共同祖先。如果不是,则返回 null。

假设每个节点都可以访问左右 child 。您可以附加节点结构,但您可以将父节点附加到每个节点。您的算法的运行时间应少于 O(N^2),其中 N 是树中的节点数。

注意:虽然它类似于著名的最不常见祖先问题,但由于其局限性,它并不完全相同。

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com