二叉树的最近公共祖先
当时刚看完王道数据结构(23版)P134的第五题
已知一棵二叉树按顺序存储结构进行存储,设计一个算法,求编号分别为i和j的两个结点的最近公共祖先结点的值
其算法描述如下 :
1
2
3
4
5
6
7
8
9
10
11
12
13
14ElemType Comm_Ancestor(SqTree T,int i,int j){ // 本算法在二叉树中查找结点i和结点j的最近公共祖先结点 if(T[i] != ‘#’ && T[j] != ‘#’){ //如果结点存在 while(i!=j){ //两个编号不同时循环 if(i > j) i = i/2; //向上找i的祖先 else j = j/2; //向上找j的祖先 } return T[i]; } }
所以看到这道题,我有一个很棒的想法,就是把二叉树转化为数组,然后根据上面的思想进行查找即可。于是有了下面又臭又长的代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { int numP=0,numQ=0; //numP,numQ分别存储P,Q的位序 TreeNode* work = root; //工作指针指向根节点 vector<TreeNode *> T; //把二叉树转化为顺序存储 T.push_back(NULL); //第一个位置为空,即索引和位序相同 queue<TreeNode *> Q; //实现顺序存储需要队列Q Q.push(work); //压入头节点 int i = 1; //用于计数 while(!Q.empty()){ //层次遍历基本操作 work = Q.front(); //取出队头 Q.pop(); T.push_back(work); //追加到数组最后 if(work){ //如果当前的树节点是非空的,不用找了,没后代 //记录要查找公共祖先的两个节点的位置 if(work == p) numP = i; if(work == q) numQ = i; //层次遍历基本操作,不同的是,如果是空的也要入队。 Q.push(work->left); Q.push(work->right); } i++; //位序加一,指向下一个数组空间 } //废了这么大力气就是把树从链表形式转化为数组 //把问题转化为了顺序存储结构的二叉树找最近公共祖先的问题 if(T[numP]&&T[numQ]){ while(numP != numQ){ if(numP > numQ) numP /= 2; else numQ /= 2; } } return T[numP]; } };
测试用例一跑,很成功,结果提交就失败了。
后来简单模拟一下才发现,这根本不是二叉树的顺序存储结构,中间许多空结点没有记录下来,直接跳掉了(能记录到非空结点的空孩子,但记录不到空结点的空孩子)
我把上一次写的求最深的拿过来,然后遍历其满二叉树的情况岂不美哉?于是有了我这题史上最????代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73class Solution { public: int maxDepth(TreeNode* root) { if (root == nullptr) return 0; queue<TreeNode*> Q; Q.push(root); int ans = 0; while (!Q.empty()) { int sz = Q.size(); while (sz > 0) { //分为内外循环,内循环每次只处理一层结点。 TreeNode* node = Q.front();Q.pop(); if (node->left) Q.push(node->left); if (node->right) Q.push(node->right); sz -= 1; } ans += 1; } return ans; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { int numP=0,numQ=0; //numP,numQ分别存储P,Q的位序 TreeNode* work = root; //工作指针指向根节点 vector<TreeNode *> T; //把二叉树转化为顺序存储 T.push_back(NULL); //第一个位置为空,即索引和位序相同 queue<TreeNode *> Q; //实现顺序存储需要队列Q Q.push(work); //压入头节点 int depth = maxDepth(root); long long one = 1; //移位超过32会报错,所以要改为long long int sumIndex = (one<<(depth))-1; //对于满二叉树的情况 int i = 1; //用于计数 while(sumIndex--){ work = Q.front(); //取出队头 Q.pop(); T.push_back(work); //追加到数组最后 if(work){ //如果当前的树节点是非空的,不用找了,没后代 //记录要查找公共祖先的两个节点的位置 if(work == p) numP = i; if(work == q) numQ = i; //层次遍历基本操作,不同的是,如果是空的也要入队。 Q.push(work->left); Q.push(work->right); }else{ // 如果结点时空的,还是要放入空位置来占位 Q.push(NULL); Q.push(NULL); } i++; //位序加一,指向下一个数组空间 } //废了这么大力气就是把树从链表形式转化为数组 //把问题转化为了顺序存储结构的二叉树找最近公共祖先的问题 if(T[numP]&&T[numQ]){ while(numP != numQ){ if(numP > numQ) numP /= 2; else numQ /= 2; } } return T[numP]; } };
中间还垂死挣扎的把int 改为 long long ,结果还是出现报错,
runtime error:shift exponent 10001 is to large for 64-bit type ‘long long’
即移位超过64位!
int32最多移动31次,64位的long long最多移动63次。
想到会爆炸,没想到爆这么大,这下啥基本数据类型都救不了了。
我知道还能优化,但是在这种屎山代码下优化简直是有病。下面来看正规解法。
DFS
官方的解法,我觉得那个这次官方题解做的挺好的,看完就懂了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution { public: TreeNode* ans; //深度优先遍历(后序) bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == nullptr) return false; bool lson = dfs(root->left, p, q); bool rson = dfs(root->right, p, q); if ((lson && rson) || ((root == p || root == q ) && (lson || rson))) { //这个判断分两种情况 //如果(1.左右子树都存在指定结点,或2.指定结点位父子关系) ans = root; } return lson || rson || (root == p || root == q); //左右孩子有指定结点,或该根就是要找到的结点时,放回True } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { dfs(root, p, q); return ans; } };
时空:O(n)
存储父结点
官方代码,主要是利用的题目的条件—Node.Value各不相同。不过不利用也可以,把key值改为结点指针即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33class Solution { public: unordered_map<int, TreeNode*> fa; //儿子的数值:父亲的结点指针 unordered_map<int, bool> vis; //结点数值:是否访问过 void dfs(TreeNode* root){ if (root->left != nullptr) { fa[root->left->val] = root; dfs(root->left); } if (root->right != nullptr) { fa[root->right->val] = root; dfs(root->right); } } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { fa[root->val] = nullptr; //根结点对应的父亲为空 dfs(root); //递归调用dfs,记录所有直系父子关系 while (p != nullptr) { //从p结点开始,往上遍历,并记录所有访问过的结点 vis[p->val] = true; p = fa[p->val]; } while (q != nullptr) { //从q结点开始,往上遍历,直到遇到p访问过的。 if (vis[q->val]) return q; q = fa[q->val]; } return nullptr; //不会执行到这里的,因为至少有一公共祖先,根结点。随便返回。 } };
时空:O(n)
最后
以上就是想人陪小甜瓜最近收集整理的关于236.二叉树的最近公共祖先(骚操作翻车记录)二叉树的最近公共祖先的全部内容,更多相关236.二叉树内容请搜索靠谱客的其他文章。
发表评论 取消回复