由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Find LeastCommonAncestor for N-ary Tree
相关主题
Lowest common ancestor of two nodes of Binary TreeAmazon phone interview Software Engineering Intern
Find the node with given value in binary tree in in-order问一个C++的binary search tree类实现问题 (转载)
least common ancestor的疑惑面试的时候 binary tree的delete也要15分钟之内写完么?
请问我写的这个判断tree是否balance的code有问题么?弱问怎么判断两个binary tree相同?
Twitter电面未通过Leetcode bst max path-----is this solution correct?
那个skiplist的题谁来给谢谢问一个问题: binary search Tree的删除用java实现。
一道老题目, 求最快捷解法求教Leetcode题目:Lowest Common Ancestor
判断 bst 疑问Find a sub tree with min weight怎么做
相关话题的讨论汇总
话题: node话题: null话题: return话题: ret话题: find
进入JobHunting版参与讨论
1 (共1页)
k***t
发帖数: 276
1
写了一个,没测试。谁给Review一下。谢了。
===========================================
#include
#include
#define N 100
struct Node {
int val;
int nC; // Num of Children
Node *c[N]; // Children
};
bool hasP=false, hasQ=false;
Node * doLCA (Node *r, Node *p, Node *q) {
Node *first=NULL, *second=NULL;
assert(p&&q);
if (!r) return NULL;
if (p==r) {hasP=true; return r;}
if (q==r) {hasQ=true; return r;}
for (int i=0;inC;i++) {
Node *t=doLCA(r->c[i], p, q);
if (t) {
if (!first) first=t;
else {
second=t;
break;
}
}
}
if (first && second) return r;
else return first;
}
Node * find (Node *r, Node *p) {
Node *ret=NULL;
assert(p);
if (!r) return NULL;
if (r==p) return r;
for (int i=0;inC;i++) {
ret = find (r->c[i], p);
if (ret) return ret;
}
return NULL;
}
Node *LCA (Node *r, Node *p, Node *q) {
Node *ret;
if (!r || !p || !q) return NULL;
if (p==q) return find(r, p);

ret=doLCA(r, p, q);
if (hasP && hasQ) return ret;
else return NULL;
}
1 (共1页)
进入JobHunting版参与讨论
相关主题
Find a sub tree with min weight怎么做Twitter电面未通过
一个老题binary tree找 lowest common ancestor 的code (请教那个skiplist的题谁来给谢谢
Lowest Common Ancestor in a binary tree (no parent pointer)一道老题目, 求最快捷解法
请教LEETCODE讲解部分的LCA一道题的变种。。判断 bst 疑问
Lowest common ancestor of two nodes of Binary TreeAmazon phone interview Software Engineering Intern
Find the node with given value in binary tree in in-order问一个C++的binary search tree类实现问题 (转载)
least common ancestor的疑惑面试的时候 binary tree的delete也要15分钟之内写完么?
请问我写的这个判断tree是否balance的code有问题么?弱问怎么判断两个binary tree相同?
相关话题的讨论汇总
话题: node话题: null话题: return话题: ret话题: find