serhatadali
BAN USERFor a given node n, call its closest parent N a "left parent" if n is on the right subtree of N, or call it "right parent" if n is on the left subtree of N.
ex:
k
\
m
/
n
for n, m is right parent, k is left parent.
for a given node n, left parent L and right parent R
function(Node n, bool isLeftChild, Node Lparent, Node Rparent)
{
if isleftChild
check if n < Rparent
check if n > Lparent
else
check if n > Lparent
check if n < R parent
function(n.left, true, Lparent, n)
function(n, n.right, n, Rparent)
}
and run it with :
function(root.left, true, null, root)
function(root.right, false, root, null)
major "duh"
- serhatadali November 01, 2012Suppose A being a subarray which already holds the criteria, and p is the adjacent member to A, currently being checked.
if p+min1 >= k /*and p+min2 >= k*/
add p to the A,
update min1 /*and min2 values. */
where min1 is the smallest member of A
/* min2 is the smallest member of A which is greater than or equal to min1.
*/
O(N)
- serhatadali November 06, 2012