c***g
发帖数: 472 | 1 binary tree找最近的共同的祖先, 怎么做?
我说先找到这两个点, 然后比较path, 但是我不知道怎么找到这两个点, 因为不是
binary search tree, 怎么找path啊?
后来对方说, 不能找path, 要用recursive的方法做, 怎么做? | r*******y
发帖数: 1081 | 2 bool IsNodeInside(TreeNode * root, TreeNode * node){
if(root==NULL)
return false;
if(node == root)
return true;
bool tmp = IsNodeInside(root->left, node);
if(tmp == true)
return true;
tmp = IsNodeInside(root->right, node);
if(tmp == true)
return true;
return false;
}
TreeNode * find(TreeNode * root, TreeNode * node1, TreeNode * node2){
if(root == NULL)
return NULL;
if(node1==root)
return root;
if(node2==root)
return root;
if(IsNodeInside(root->left, node1) && IsNodeInside(root->right,
node2))
return root;
if(IsNodeInside(root->left, node2) && IsNodeInside(root->right,
node1))
return root;
if(IsNodeInside(root->left, node1) && IsNodeInside(root->left, node2
))
return find(root->left, node1, node2);
if(IsNodeInside(root->right,node1) && IsNodeInside(root->right,
node2))
return find(root->right, node1, node2);
}
It is a kind of stupid code. I believe there is a better and smarter one
}
【在 c***g 的大作中提到】
: binary tree找最近的共同的祖先, 怎么做?
: 我说先找到这两个点, 然后比较path, 但是我不知道怎么找到这两个点, 因为不是
: binary search tree, 怎么找path啊?
: 后来对方说, 不能找path, 要用recursive的方法做, 怎么做?
| a********e
发帖数: 508 | 3 为啥不能找path？找path比recursive快吧
【在 c***g 的大作中提到】
: binary tree找最近的共同的祖先, 怎么做?
: 我说先找到这两个点, 然后比较path, 但是我不知道怎么找到这两个点, 因为不是
: binary search tree, 怎么找path啊?
: 后来对方说, 不能找path, 要用recursive的方法做, 怎么做?
| c***g
发帖数: 472 | 4 是啊, 白痴面试人, 我说,recurisve不是过程一样的, 而且更慢么?
【在 a********e 的大作中提到】
: 为啥不能找path？找path比recursive快吧
|
|
