- 浏览: 400470 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
handong1587:
代码有一处错.query函数最后一行return的应该是:re ...
RMQ -
yuandong0828:
简洁的特别透彻细致,多谢,
虚函数、虚指针和虚表 -
adam_zs:
谢谢分享!
括号匹配问题 -
hongloumengyanzxw:
good[b][/b]
dup和dup2函数 -
chriszeng87:
最后第二种情况右下角的那个点是不是可以看作相交点的?上面的那种 ...
判断两个链表是否相交
求二叉树中任意两个节点的最近公共祖先也称为LCA问题(Lowest Common Ancestor)。
二叉查找树
如果该二叉树是二叉查找树,那么求解LCA十分简单。
基本思想为:从树根开始,该节点的值为t,如果t大于t1和t2,说明t1和t2都位于t的左侧,所以它们的共同祖先必定在t的左子树中,从t.left开始搜索;如果t小于t1和t2,说明t1和t2都位于t的右侧,那么从t.right开始搜索;如果t1<t< t2,说明t1和t2位于t的两侧,那么该节点t为公共祖先。
如果t1是t2的祖先,那么应该返回t1的父节点;同理,如果t2是t1的祖先,应该返回t2的父节点。
public int query(Node t1, Node t2, Node t) { int left = t1.value; int right = t2.value; Node parent = null; if (left > right) { int temp = left; left = right; right = temp; } while (true) { if (t.value < left) { parent = t; t = t.right; } else if (t.value > right) { parent = t; t = t.left; } else if (t.value == left || t.value == right) { return parent.value; } else { return t.value; } } }
其中,parent用于处理t1是t2的祖先(或t2是t1的祖先)的情况。
一般的二叉树
如果二叉树不是二叉查找树该怎么办呢?
1. 离线算法(Tarjan)
利用并查集优越的时空复杂度,可以实现O(n+q)的算法,q是查询次数。
Tarjan算法基于深度优先搜索。对于新搜索到的一个结点u,先创建由u构成的集合,再对u的每颗子树进行搜索,每搜索完一棵子树,这时候子树中所有的结点的最近公共祖先就是u了。
void LCA(int parent) //从根节点开始 { p[parent] = parent; ancestor[findSet(parent)] = parent; for(int i = index[parent]; i != -1; i = e[i].next) { LCA(e[i].to); Union(parent,e[i].to); ancestor[findSet(parent)] = parent; } vis[parent] = true; if(parent == a && vis[b]) //要先将所有查询记录下来,这里只有一个查询:a与b的LCA printf("%d\n",ancestor[findSet(b)]); else if(parent == b && vis[a]) printf("%d\n",ancestor[findSet(a)]); }
2. 在线算法(RMQ)
一个O(nlog2n)的预处理,O(1)的查询。
以下面一棵树为例:
(1)
/ \
(2) (7)
/ \ \
(3) (4) (8)
/ \
(5) (6)
step1:
按深度遍历树,记录访问顺序和相应的深度(2*n-1),及每个节点第一次出现的位置。
结点的访问顺序为:1 2 3 2
4 5 4 6 4 2 1 7 8 7
相应的深度为: 0 1 2 1
2 3 2 3
2 1 0 1 2 1 0
结点1-8第一次出现的次序为:1 2 3 5 6 8 12 13
step2:
查询3和6的公共祖先,考虑3和6第一次出现的位置为3和8,即寻找序列2 1 2 3 2 3中的最小值,最小值为1,对应的点位2,则3与6的最近公共祖先为2。
step3:
则对于给出的任意两个结点,找出它们第一次出现的位置i,j(i<j),在深度序列中查询最小值的下标k,depth[k]即为所求。显然,查询多次深度序列中的最小值的下标,自然而然就想到了RMQ。
public class LCA { private final int MAX = 10; private int[] dfs = new int[2*MAX]; private int[] depth = new int[2*MAX]; private int[][] f; private int[] call = new int[MAX]; private int len = 0; public void track(Node t, int d) { if (t == null) return; dfs[len] = t.value; depth[len] = d; call[t.value-1] = len; len++; track2(t.left, d+1); if (t.left != null) { dfs[len] = t.value; depth[len] = d; len++; } track2(t.right, d+1); if (t.right != null) { dfs[len] = t.value; depth[len] = d; len++; } } public void rmq() { int count = 1; while ((1 << count) <= len) count++; f = new int[len][count]; count--; for (int i = 0; i < len; i++) { f[i][0] = i; } for (int j = 1; (1 << j) <= len; j++) { for (int i = 0; i+(1<<j)-1 < len; i++) { f[i][j] = depth[f[i][j-1]] < depth[f[i+(1<<j-1)][j-1]] ? f[i][j-1] : f[i+(1<<j-1)][j-1]; } } } public int query(Node t1, Node t2) { int start = call[t1.value-1]; int end = call[t2.value-1]; if(start > end) { int temp = start; start = end; end = temp; } int count = 1; while ((1 << count) <= end - start + 1) count++; count--; int result = depth[f[start][count]] < depth[f[end-(1<<count)+1][count]] ? f[start][count] : f[end-(1<<count)+1][count]; if (dfs[result] == t1.value || dfs[result] == t2.value) { int temp = depth[result]; while (depth[result] >= temp) result--; } return dfs[result]; } public static void main(String[] args) { Node n3 = new Node(3); Node n5 = new Node(5); Node n6 = new Node(6); Node n4 = new Node(4, n5, n6); Node n2 = new Node(2, n3, n4); Node n8 = new Node(8); Node n7 = new Node(7, null, n8); Node n1 = new Node(1, n2, n7); LCA l = new LCA(); l.track(n1, 0); l.rmq(); System.out.println(l.query(n5, n4)); } } class Node { int value; Node left; Node right; public Node(int value, Node left, Node right) { this.value = value; this.left = left; this.right = right; } public Node(int value) { this.value = value; this.left = null; this.right = null; } }
3. 后序遍历
基本思想:如果这两个节点不在一条线上(即这两个节点不存在一个节点是另一个节点的祖先的情况),则它们必定分别在所求节点A的左子树和右子树上,后序遍历到第一个满足这个条件的节点就是所要求的节点A。否则,当这两个节点在一条线上,所求节点A则是这两个节点中深度最低的节点的父节点。
bool lca(Node *root, int va, int vb, Node *&result, Node* parent) { // left/right 左/右子树是否含有要判断的两节点之一 bool left = false, right = false; if (!result && root->left) left = lca(root->left,va,vb,result,root); if (!result && root->right) right = lca(root->right,va,vb,result,root); // mid 当前节点是否是要判断的两节点之一 bool mid = false; if (root->data == va || root->data == vb) mid=true; if (!result && int(left + right + mid) == 2) { if (mid) result = parent; else result = root; } return left | mid | right ; } Node *query(Node *root,int va, int vb) { if (root == NULL) return NULL; Node *result = NULL; lca(root, va, vb,result, NULL); return result; }
发表评论
-
最长公共子序列
2011-10-09 18:15 1203题目 如果字符串1中的所有字符都按顺序的出现在字符串 ... -
弗洛伊德算法
2011-10-07 20:38 5392Floyd-Warshall算法,简称Floyd算法,用于求解 ... -
最大栈和最大队列
2011-10-04 20:50 3617最大栈 具有栈的功能,并且提供O(1)的时间复杂度来获 ... -
楼层扔鸡蛋问题
2011-10-03 13:44 1961有限层数和蛋数,求即使最坏情况下需要的最少判断次数 ... -
判断两个链表是否相交
2011-10-02 15:44 4887题目 : 给出两个链表的头指针,比如h1,h2,判断 ... -
求和为n的连续正整数序列
2011-09-27 18:49 2300题目:输入一个正数n,输出所有和为n连续正整数序列。 ... -
并查集
2011-09-25 22:07 10131. 概述 并查集(Disjoi ... -
映射二分堆
2011-09-18 20:57 3118引入 平常,我们用堆最常见的就是随机地加入元素, ... -
在两个有序数组中找第N数
2011-09-14 22:32 6150给定两个有序的数组,长度分别为m和n,求这两个数组中的第K个元 ... -
寻找树形图中的最长路径
2011-09-14 16:06 8460题目: 在一个迷宫中找距离最长的两个点。 迷宫可以看 ... -
复制链表
2011-09-13 22:52 1684题目:已知一链表,每个节点除了有一个指向下一节点的指针外,还有 ... -
二分查找数组中的转折点
2011-09-13 16:27 1618有一个有序的数组,将其中的元素都右移X位,这样将该数组变成了一 ... -
树的非递归先序遍历
2011-09-12 22:08 1585对于树的遍历操作,通常使用递归的方式写起来比较简单。但是偶尔也 ... -
RMQ
2011-09-12 21:50 1429RMQ英文是Range Maximum(Minimum) Qu ... -
括号匹配问题
2011-09-06 11:54 1452括号匹配问题: import java.util.St ... -
Trie树
2011-09-05 21:40 4331Trie树,又称字典树,单词查找树或者前缀树,是一种用于快速检 ... -
链表逆序
2011-09-03 00:02 1148链表逆序,即将原先的链表 a->b->c-> ... -
海量数据面试题
2011-08-28 14:44 11961. 给定a、b两个文件, ... -
一些和图论有关的算法
2011-07-17 19:10 18981. 拓扑排序 算法:首先对每个顶点计算它的入度。然后 ... -
几个经典算法的概念
2011-06-11 18:13 1436动态规划(Dynamic Programming) ...
相关推荐
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)” 例如,给定如下二叉树: root = [3...
(1)拟定合适的二叉树的输入形式和构造算法; (2)能够以直观的形式观察所建立的二叉树的结构;
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节
中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以
本程序包括二叉树的一些常见的相关操作,比如非递归建立二叉树,二叉树的非递归遍历,非递归求二叉树的叶子数目,层数,任意两个节点的公共祖先,跟到叶子节点的所有路径,根据中序和后序的遍历结果建立二叉树等等。
//求二叉树的节点个数//前序打印叶子节点//二叉树的遍历//求二叉树的第k层节点的值//交换二叉树的左右子树//求二叉树中两个节点的最低公共祖先节点//求双亲节点//判断两棵二叉树是否相同//二叉树删除节点//二叉树...
因为树的结构不同所以需要分情况...当树为二叉排序树,寻找给定两节点的最低公共祖先 当树为普通树,每个节点中有指针指向其父节点 当树为二叉树,每个节点仅有左右孩子指针 当树为普通树,每个节点仅有左右孩子指针
由于二叉树中每个结点都可能有两个子树,因此需要寻找一条合适的搜索路径。 1、前序遍历 前序遍历二叉树操作定义为: 若树为空,则空操作返回;否则 (1)访问根结点 (2)前序遍历根结点的左子树 (3)前序遍历根...
如何求二叉树的任意两个节点的公共祖先,可以通过编译
12.从文件中读出所有节点信息到一个数组中,然后按一年中生日的先后进 行快速排序。 13、按姓名查询家谱成员并显示该成员的各项信息。 14、给出某一成员的姓名,删除该成员和该成员的所有子孙。 15、成员信息的...
直径或宽度(树中任意两个节点之间的最长距离) 二叉树节点的组成部分 它保存的数据类型,例如Int或String等 指向左子节点的指针 指向右子节点的指针 常见操作 遍历 插入 删除 二叉树节点 class BinaryTreeNode <...
在排序数组中查找数字.py 二叉搜索树的第k大节点.py 二叉树的深度.py 数组中数字出现的次数.py 和为s的数字.py 翻转字符串.py 队列的最大值.py n个骰子的点数.py ...树中两个节点的最低公共祖先.py
平衡二叉树是在构造二叉排序树的过程中,每当插入一个新结点时,首先检查是否因插入新结点而破坏了二叉排序树的平衡性,若是,则找出其中的最小不平衡子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各...
50. 树中两个节点的最低公共祖先 51. 找出重复的数 52. 构建乘积数组 53. 正则表达式匹配 54. 表示数值的字符串 55. 字符流中第一个不重复的字符 56. 链表中环的入口节点 57. 删除链表中重复的节点 58. ...
1. 一根木棒截成三段,能组成三角形的概率 2. · 找二叉树中任意两个节点的最近公共祖先 3. · 推导一下逻辑回归算法,如何得到 loss function
50.第一个只出现一次的字符 50.字符流中第一个不重复的字符 51.数组中的逆序对 Array 常考 52.两个链表的第一个公共结点 Linked List 53.数字在排序数组中出现的次数 ...68.树中两个节点的最低公共祖先 常考
树木二叉搜索树验证从排序数组创建二叉搜索树为给定的二叉树创建每个深度的所有节点的链表在 BST 中按顺序查找节点的后继查找二叉树中两个节点的共同祖先返回二叉树中总和为给定值的所有路径检查二叉树是否平衡检查...
二叉树的最近公共祖先 路径总和II 打家劫舍III 没做出来。动态规划算法 二叉树的垂序遍历 删除二叉搜索树中的节点 移除链表元素 环形链表 回文链表 环形链表 II 两两交换链表中的节点 对...