e*****e
发帖数: 1275 | 1 There is a binary tree(Not a BST) in which you are given three nodes x,y,z .
Write a function which finds whether y lies in the path b/w x | m*********1
发帖数: 112 | | j*****u
发帖数: 1133 | 3 easy if Node has a parent pointer
if not, do a recursive traversal and maintain a set that contains the nodes
from root to current, and check x,y,z in the set during traversal. If we eve
r see nodes get added into set following x->z->y or or y->z->x order, we kno
w z is on the path between x and y. Time: O(N), Space: O(logN)
.
【在 e*****e 的大作中提到】
: There is a binary tree(Not a BST) in which you are given three nodes x,y,z .
: Write a function which finds whether y lies in the path b/w x
| w*z
发帖数: 75 | 4 how about z is the parent of x and y, and x and y are in different subtrees
站: BBS 未名空间站 (Fri Feb 4 00:49:26 2011, 美东)
nodes
eve
kno
,z
【在 j*****u 的大作中提到】
: easy if Node has a parent pointer
: if not, do a recursive traversal and maintain a set that contains the nodes
: from root to current, and check x,y,z in the set during traversal. If we eve
: r see nodes get added into set following x->z->y or or y->z->x order, we kno
: w z is on the path between x and y. Time: O(N), Space: O(logN)
:
: .
| j*****u
发帖数: 1133 | 5 Then I misunderstood the question, in this case
1. Get path from root -> x and root -> y
2. Get the lowest common ancestor w of x and y
3. Check if z is on x -> w or w -> y
Complexity is still the same
subtrees
【在 w*z 的大作中提到】
: how about z is the parent of x and y, and x and y are in different subtrees
:
: 站: BBS 未名空间站 (Fri Feb 4 00:49:26 2011, 美东)
: nodes
: eve
: kno
: ,z
|
|
