「公共祖先java」公共祖先可以是自己吗
今天给各位分享公共祖先java的知识，其中也会对公共祖先可以是自己吗进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
如何求二叉树最接近的共同祖先
【以下转载自网络】
首先，题目中没有明确说明节点的结构，所以这里分这两种情况讨论：
1. 二叉树节点具有父指针
在节点具有父指针的情况下，显然此二叉树就可以看成是通过父指针连接的"T"型链表，题目也就转化成查找"T"型链表的第一个公共节点。假设p，q分别为所求的两个节点，则通过遍历一遍可以知道p，q分别到根节点的长度pLen和qLen。这样就知道pLen和qLen之间长度之差，也就知道p、q到它们的第一个公共祖先节点k长度之差L。因为p，q到根节点的路径中都包含k到根节点的路径，所以pLen和qLen之差等于p、q到k的长度之差。然后，让p、q到根节点路径长度大的先向前走L，然后长度小再和大的同时向前遍历，当它们两指向同一个节点时，则那个节点即是所求。
[java] view plaincopyprint?
/**
* 有父指针情况下，查找两个节点的最低公共节点
* @author chosen0ne
* 2011-01-18
*/
class BTreeT{
private BTNodeT root;
public BTree(BTNodeT r){
this.root=r;
}
/**
* 查找两个节点的最低公共祖先节点
* @param p
* @param q
* @return BTNodeT 最低公共祖先节点，没有找到返回null
*/
public BTNodeT findLowestAncestor(BTNodeT p,BTNodeT q){
if(p==null||q==null)
throw new NullPointerException();
int pLen=0,qLen=0;//p，q两个节点到根节点的路径长度
//计算p到根节点的长度
for(BTNodeT ancestor=p.parent;ancestor!=null;ancestor=ancestor.parent)
pLen++;
//计算q到根节点的长度
for(BTNodeT ancestor=q.parent;ancestor!=null;ancestor=ancestor.parent)
qLen++;
//如果p到根节点的长度比q长，则让p前进pLen-qLen
for(;pLenqLen;pLen--)
p=p.parent;
//如果q到根节点的长度比p长，则让q前进qLen-pLen
for(;qLenpLen;qLen--)
q=q.parent;
//此时，p和q到根节点的长度相同。假设k是最近的公共节点，则p和q到k的长度相同
//p和q按照相同步长1向前遍历，如果存在公共节点则p和去会同时指向它
while(q!=nullp!=nullp!=q){
q=q.parent;
p=p.parent;
}
if(p==q)
return p;
return null;
}
/**
* 测试方法，在t中查找a，b的最低公共祖先节点
* @param t
* @param a
* @param b
*/
private staticT void test(BTreeT t, BTNodeT a, BTNodeT b){
BTree.BTNodeT p=t.findLowestAncestor(b,a);
if(p!=null)
System.out.println(a.data+","+b.data+"的最低公共祖先节点是 ："+p.data);
else
System.out.println(a.data+","+b.data+"没有公共祖先节点");
}
public static void main(String[] arg){
/* 构造如下二叉树
a
/ /
b c
/ / / /
d e f g
*/
BTree.BTNodeString g=new BTree.BTNode().data("g");
BTree.BTNodeString f=new BTree.BTNode().data("f");
BTree.BTNodeString e=new BTree.BTNode().data("e");
BTree.BTNodeString d=new BTree.BTNode().data("d");
BTree.BTNodeString c=new BTree.BTNode().data("c").left(f).right(g);
f.parent(c);
g.parent(c);
BTree.BTNodeString b=new BTree.BTNode().data("b").left(d).right(e);
d.parent(b);
e.parent(b);
BTree.BTNodeString a=new BTree.BTNode().data("a").left(b).right(c);
b.parent(a);
c.parent(a);
BTreeString t=new BTreeString(a);
test(t,c,f);
}
static class BTNodeT
{
BTNodeT left;
BTNodeT right;
BTNodeT parent;
T data;
public BTNode(){}
public BTNode(BTNodeT l,BTNodeT r,BTNodeT p,T d){
this.left=l;
this.right=r;
this.parent=p;
this.data=d;
}
BTNodeT left(BTNodeT l){
this.left=l;
return this;
}
BTNodeT right(BTNodeT r){
this.right=r;
return this;
}
BTNodeT parent(BTNodeT p){
this.parent=p;
return this;
}
BTNodeT data(T d){
this.data=d;
return this;
}
}
}
2.二叉树节点不具有父指针
这种情况下，必须通过遍历查找一个节点的祖先集合，然后比较两个节点的祖先集合就可以找到最低的那个。这里采用后序遍历，并传入一个栈记录该节点的祖先节点。在每次访问一个节点时，先把这个节点压入栈，然后判断该节点是不是要查找的那个节点，如果是返回。接着查找它的左子树和右子树，当要查找的节点在它的左右子树中则返回。然后判断该节点与栈顶节点是否相同，是则弹出栈顶元素。这是因为相同就代表了在访问它的左右子树时没有添加新的节点，也就是说要查找的那个节点不在它的左右子树中，则该节点也就是不是要查找的节点的祖先。
[java] view plaincopyprint?
import java.util.ArrayList;
/**
* 没有父指针情况下，查找两个节点的最低公共节点
* @author chosen0ne
* 2011-01-18
*/
class BTreeT
{
private BTNodeT root;
public BTree(BTNodeT r){
this.root=r;
}
/**
* 查找两个节点的最低公共祖先节点
* @param p
* @param q
* @return BTNodeT 最低公共祖先节点，没有找到返回null
*/
public BTNodeT findLowestAncestor(BTNodeT p,BTNodeT q){
if(p==null||q==null)
throw new NullPointerException();
ArrayListBTNodeT sp=new ArrayListBTNodeT();
ArrayListBTNodeT sq=new ArrayListBTNodeT();
travalPostOrder(root,p,sp);
travalPostOrder(root,q,sq);
//祖先栈中，以先后顺序存储，所以这里倒序来遍历以便找到最低的那个祖先节点
for(int i=sp.size()-1;i=0;i--)
for(int j=sq.size()-1;j=0;j--)
if(sp.get(i)==sq.get(j))
return sp.get(i);
return null;
}
/**
* 后序遍历二叉树，进行节点的搜索，当搜索成功时，将该节点的所有祖先存入栈中
* @param n 遍历的节点
* @param p 欲搜索的节点
* @param stack 存储祖先节点的栈，这里使用ArrayList，因为后续查找最低公共祖先时需要遍历所有元素
* @return boolean 是否搜索到该节点
*/
private boolean travalPostOrder(BTNodeT n,BTNodeT p,ArrayListBTNodeT stack){
if(n!=null){
stack.add(n);
if(n==p)
return true;
if(travalPostOrder(n.left,p,stack))
return true;
if(travalPostOrder(n.right,p,stack))
return true;
int lastIndex=stack.size()-1;
//如果搜索完n的左右子树后，栈顶还是n，则代表n不是p的祖先节点，所以将n从栈中删除
if(n==stack.get(lastIndex)){
stack.remove(lastIndex);
}
}
return false;
}
/**
* 测试方法，在t中查找a，b的最低公共祖先节点
* @param t
* @param a
* @param b
*/
private staticT void test(BTreeT t, BTNodeT a, BTNodeT b){
BTree.BTNodeT p=t.findLowestAncestor(b,a);
if(p!=null)
System.out.println(a.data+","+b.data+"的最低公共祖先节点是 ："+p.data);
else
System.out.println(a.data+","+b.data+"没有公共祖先节点");
}
public static void main(String[] arg){
/* 构造如下二叉树
a
/ /
b c
/ / / /
d e f g
*/
BTree.BTNodeString g=new BTree.BTNode().data("g");
BTree.BTNodeString f=new BTree.BTNode().data("f");
BTree.BTNodeString e=new BTree.BTNode().data("e");
BTree.BTNodeString d=new BTree.BTNode().data("d");
BTree.BTNodeString c=new BTree.BTNode().data("c").left(f).right(g);
BTree.BTNodeString b=new BTree.BTNode().data("b").left(d).right(e);
BTree.BTNodeString a=new BTree.BTNode().data("a").left(b).right(c);
BTreeString t=new BTreeString(a);
test(t,a,b);
}
static class BTNodeT
{
BTNodeT left;
BTNodeT right;
T data;
public BTNode(){}
public BTNode(BTNodeT l,BTNodeT r,T d){
this.left=l;
this.right=r;
this.data=d;
}
BTNodeT left(BTNodeT l){
this.left=l;
return this;
}
BTNodeT right(BTNodeT r){
this.right=r;
return this;
}
BTNodeT data(T d){
this.data=d;
return this;
}
}
}
在没有父指针时，还可以给每个节点添加一个计数器，在进入一个节点时加1，在退出该节点时减1。访问该节点时，如果要查找的节点在该节点的子树中，则返回。实际上，这和上面的算法思想是一样的，只是实现不同。
这两种算法的时间复杂度都是O(n)，效率不错。没有父指针的情况，空间复杂度也是O(n)。
字节面试什么都不会
为何你面试字节跳动屡次惨败？其实都是“算法”在搞鬼，可惜你却一直傻傻不知道！那么，这回就一次性分享够，二叉树、链表、字符串、栈和队列等等各大面试高频知识点全部总结给你。
注意：需要分享的这些全部算法资料的朋友可以私信 “算法” 免费领取，小编会一一回复大家的哟~
20个二叉树面试高频
0. 几个概念
1. 求二叉树中的节点个数
2. 求二叉树的最大层数(最大深度)
3. 先序遍历/前序遍历
4. 中序遍历
5. 后序遍历
6. 分层遍历
7. 求二叉树第K层的节点个数
8. 求二叉树第K层的叶子节点个数
9. 判断两棵二叉树是否结构相同
10. 判断二叉树是不是平衡二叉树
11. 求二叉树的镜像
12. 求二叉树中两个节点的最低公共祖先节点
13. 求二叉树的直径
14. 由前序遍历序列和中序遍历序列重建二叉树
15. 判断二叉树是不是完全二叉树
16. 树的子结构
17. 二叉树中和为某一值的路径
18. 二叉树的下一个结点
19. 序列化二叉树
20. 二叉搜索树的第k个结点
21二叉树
算法刷题LeetCode中文版：二叉树
算法刷题LeetCode中文版：二叉树
17个链表面试高频
1. 在 O(1) 时间删除链表节点
2. 翻转单链表
3. 翻转部分单链表
4. 旋转单链表
5. 删除单链表倒数第 n 个节点
6. 求单链表的中间节点
7. 链表划分
8. 链表求和
9. 单链表排序
10. 合并两个排序的链表
11. 复杂链表的复制
12. 删除链表中重复的结点
13. 判断单链表是否存在环
14. 单链表是否有环扩展：找到环的入口点
15. 判断两个无环单链表是否相交
16. 两个链表相交扩展：求两个无环单链表的第一个相交点
17. 两个链表相交扩展：判断两个有环单链表是否相交
17链表
算法刷题LeetCode中文版：链表
算法刷题LeetCode中文版：链表
7个堆栈和队列面试高频
1.基础概念
2.栈的 java 实现
3.队列的 java 实现
4.用两个栈实现队列
5.用队列实现栈
6.包含min函数的栈
7.栈的压入、弹出序列
7堆栈和队列
算法刷题LeetCode中文版：栈和队列
算法刷题LeetCode中文版：栈和队列
13个字符串面试高频
1. KMP 算法
2. 替换空格
3. 最长公共前缀
4. 最长回文串
5. 字符串的排列
6. 打印字符串的全排列
7. 第一个只出现一次的字符
8. 翻转单词顺序列
9. 旋转字符串
10. 把字符串转换成整数
11. 正则表达式匹配
12. 表示数值的字符串
13. 字符流中第一个不重复的字符
13个字符串面试高频答案解析
13字符串
算法刷题LeetCode中文版：字符串
参加ACM大赛应该准备哪些课程？
课程：
（1）基本算法: 二分,分治，贪心
（2） 离散数学离散数学动态规划
（3） 搜索算法：深度优先 搜索，广度优先搜 A*算法 ，阿尔法贝塔剪枝
（4）数据结构: 线段树, 树状数组，并查集,Trie图
（5）图论问题：最小生成树 最短路 强连通分量、桥和割点
（6）网络流算法：基本的网络流算法，Dinic算法，带上下界的网络流，最小费用流
（7）计算几何：线与线求交，线与面求交，求凸包，半平面求交等
（8） 离散数学，高等数学，线性代数，初等数论，计算几何
（9）计算机专业英语
（10）C++；基础的递归、枚举算法
扩展资料：
1.参赛队伍最多由三名参赛队员组成。
2.竞赛中命题10题左右，试题描述为英文，比赛时间为5个小时，前四个小时可以实时看到排名，最后一小时封榜，无法看到排名。
3.竞赛可以使用的语言：Java, C, C++, Kotlin 和 Python。
4.重点考察选手的算法和程序设计能力，不考察实际工程中常用的系统编程，多线程编程等等；
5.选手可携带任何非电子类资料，包括书籍和打印出来的程序等，部分赛区会对选手携带的纸质资料做限制。
6.评委负责将结果（正确或出错的类型）通过网络尽快返回给选手，除此之外不提供任何额外帮助；
7.每个题目对应一种颜色的气球，通过该题目的队伍会得到对应颜色气球。每道题目第一支解决掉它的队还会额外获得一个“FIRST PROBLEM SOLVED”的气球。
参考资料：北京大学暑期课：ACM/ICPC竞赛训练
百度百科-ACM国际大学生程序设计竞赛
公共祖先java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于公共祖先可以是自己吗、公共祖先java的信息别忘了在本站进行查找喔。
发布于：2022-11-26，除非注明，否则均为原创文章，转载请注明出处。