Question with the last test case in Java.


  • 0
    X

    It is the last test case (test case number as 31 I remember).
    I'm using Java. If you use a different language and (I don't know) have a different test case, please ignore my question.

    In this test case, p.val==91, and q.val==93. There are more than 2000 nodes given in the serialization of the tree, roughly half of them being null.

    My program gives 91. However the OJ says it should be 10. I looked into it. There is a node with val==91 and depth==9 (the root is considered to have depth 0, and each node has depth 1 smaller than its children) that has 91 and 93 as descendants (itself being considered one of its descendants, according to the description). There are six nodes with value 10, their depths being 1,7,8,9,11,13, among which, the ones with depths 9, 11, and 13 do not have both 91 and 93 as descendants.

    I'm doing an in-order traverse of the tree. Let's first assume that the values of nodes are distinct. Now list all the non-null nodes in the order of in-order traverse (I don't actually form a list, but just to say it for convenience), for any two nodes that appear in the list, their least common ancestor is the (unique) one between them in the list (both of them included) that has minimum depth (it's not hard to keep track of the depth of each node in the traversal). If the values are not distinct and p.val and/or q.val appear multiple times, or p.val==q.val, just some simple modifications are needed. I'm not posting my program since I don't think anyone is taking the trouble to read it (or even this post).

    I saw many posts that first dive into the left subtree and then the right subtree. So now I'm aware of that although I have doubts... (in case the depth is not well maintained, a result "deep" in the left subtree could be replaced by a "shallow" result in the right subtree... anyway, I didn't think about it carefully. Forget about it).

    So... why am I wrong ... or does anyone also get 91 for the last one?


  • 0
    X

    I read some of the solutions, and it seems there are two ways of understanding the question. So now we are given a tree with root, and p.val, q.val. For simplicity, let's suppose p.val != q.val, and there are two different ways to understand the question.

    1. Return the lowest node r, so that one descendant of r (including r itself) has value equal to p.val, and one descendant of r has value equal to q.val.

    2. Find ALL nodes that have value equal to either p.val or q.val, and return the LCA of ALL the nodes found.

    Which one is correct?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.