二叉搜索树的最低公共祖先在长输入情况下失败

Question

问题

给定二叉搜索树 (BST)，找到 BST 中两个给定节点的最低公共祖先 (LCA) 节点。

根据维基百科上LCA的定义： “最低公共祖先被定义在两个节点 p 和 q 之间，作为 T 中具有以下特征的最低节点： p 和 q 都是后代（我们允许一个节点成为其自身的后代）。”

问题陈述链接

逻辑

有两个路径队列（基于二叉搜索树逻辑遍历），然后遍历两个队列，一旦发现差异就返回前一个节点。我知道你可以使用 BST 逻辑在没有队列的情况下以某种方式完成它，我最终会优化它。但我只是想知道为什么这不起作用。

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        queueForp = collections.deque()
        queueForq = collections.deque()
        phead = root
        qhead = root
        while phead != None:
            queueForp.append(phead)
            if phead == p:
                phead = None
            else:
                if phead.val < p.val:
                    phead = phead.right
                else:
                    phead = phead.left

        while qhead!= None:
            queueForq.append(qhead)
            if qhead == q:
                qhead = None
            else:
                if qhead.val < q.val:
                    qhead = qhead.right
                if qhead.val > q.val:
                    qhead = qhead.left
        print(queueForp)
        print(queueForq)
        prev = None
        while len(queueForp)!= 0 and len(queueForq) != 0:
            currp = queueForp.popleft()
            currq = queueForq.popleft()
            if currp.val == currq.val:
                prev = currp
            else:
                return prev
        
        
        return prev

问题

在大约 10k 的大输入上失败

https://imgur.com/a/tvmp9wM

p = 5893
q = 3379

输出：41 预计：5734 或者，您可以尝试将此代码放入 leetcode 中并获取测试用例。 我做错了什么？

Answer 1

// Recursive Java program to print lca of two nodes

// A binary tree node
class Node {
    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    /* Function to find LCA of n1 and n2. The function
    assumes that both n1 and n2 are present in BST */
    Node lca(Node node, int n1, int n2)
    {
        if (node == null)
            return null;

        // If both n1 and n2 are smaller than root, then LCA
        // lies in left
        if (node.data > n1 && node.data > n2)
            return lca(node.left, n1, n2);

        // If both n1 and n2 are greater than root, then LCA
        // lies in right
        if (node.data < n1 && node.data < n2)
            return lca(node.right, n1, n2);

        return node;
    }

    /* Driver code */
    public static void main(String args[])
    {
        // Let us construct the BST shown in the above
        // figure
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(20);
        tree.root.left = new Node(8);
        tree.root.right = new Node(22);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(12);
        tree.root.left.right.left = new Node(10);
        tree.root.left.right.right = new Node(14);

        // Function calls
        int n1 = 10, n2 = 14;
        Node t = tree.lca(tree.root, n1, n2);
        System.out.println("LCA of " + n1 + " and " + n2
                        + " is " + t.data);

        n1 = 14;
        n2 = 8;
        t = tree.lca(tree.root, n1, n2);
        System.out.println("LCA of " + n1 + " and " + n2
                        + " is " + t.data);

        n1 = 10;
        n2 = 22;
        t = tree.lca(tree.root, n1, n2);
    }
}