binrengoog
BAN USERNot sure whey unLock needs O(log n), maybe i misunderstood the questions.
class TreeNode{
public TreeNode Parent = null;
public TreeNode[] Children = null;
private bool isLocked = false;
public bool IsLock(){
return isLocked;
}
public void Lock(){
if(isLocked) return;
TreeNode tn = this;
while(tn.Parent != null && !tn.IsLock())
tn = tn.Parent;
bool ancestorlocked = tn.Parent != null || tn.IsLock();
if(ancestorlocked) return;
if(!isDescendantsLock(this)){
isLocked = true;
}
}
bool isDescendantsLock(TreeNode tn){
if(tn.Children == null || tn.Children.Length < 1) return tn.IsLock();
bool locked = tn.IsLock();
foreach(TreeNode n in tn.Children){
locked |= isDescendantsLock(n);
if(locked) break;
}
return locked;
}
public void UnLock(){
isLocked = false;
}
}
Correct the mistake:
Set up 2 pointers r_start, r_end. r_start will first move M steps, then r_end moves M then N steps. Reset next values and repeat.
Set up 2 pointers r_start, r_end. r_start will first move M steps, then r_end moves N steps. Reset next values and repeat.
Node processLinkList(Node firstNode, int M, int N){
Node r_start = firstNode;
Node r_end = firstNode;
while(true)
{
int m = M, n = N;
while(m-- > 0)
{
if(r_start.Next == null)
break;
r_start = r_start.Next;
}
if(m > 0) break;
while(n-- > 0)
{
if(r_end.Next == null)
break;
r_end = r_end.Next;
}
if(n > 0) {
r_start.Next = null;
break;
}
else {
r_start.Next = r_end;
r_start = r_end;
}
}
return firstNode;
}
Does this work?
Array<Node> paths;
Node root, start, end;
function searchNode(Node node){
if (node.Value greater than end.Value) then
return;
if(node.Left is not null) then
searchNode(node.Left);
end if
if(node.Value greater than start.Value AND node.Value less than end.Value) then
paths.push(node);
if(node.Right != null) then
searchNode(node.Right)
end if
}
searchNode(root);
Also try this:
- binrengoog March 28, 2011