首页 > 代码库 > 淘宝笔试题:一颗完全二叉树,要求给所有节点加上一个pNext指针,指向同一层的相邻节点;如果当前节点已经是该层的最后一个节点,则将pNext指针指向NULL
淘宝笔试题:一颗完全二叉树,要求给所有节点加上一个pNext指针,指向同一层的相邻节点;如果当前节点已经是该层的最后一个节点,则将pNext指针指向NULL
题目:对于一颗完全二叉树,要求给所有节点加上一个pNext指针,指向同一层的相邻节点;如果当前节点已经是该层的最后一个节点,则将pNext指针指向NULL;给出程序实现,并分析时间复杂度和空间复杂度。
运用队列,按层遍历,每次遍历一层时,添加新指针,由于每个节点只需要进队一次出队一次,时间复杂度为O(n),空间复杂度为O(n),具体代码如下:
#include<iostream> #include<vector> #include<queue> using namespace std; struct BinaryTreeNode { int data; BinaryTreeNode* pNext; BinaryTreeNode* lchild,*rchild; BinaryTreeNode(int x):data(x),pNext(NULL),lchild(NULL),rchild(NULL){} }; void addNextPoint(BinaryTreeNode* root) { if(root == NULL)return; queue<BinaryTreeNode*> q; q.push(root); while(!q.empty()) { int levelLength = q.size();//当前层的节点个数 BinaryTreeNode* first = NULL,*second = NULL;//每次取两个元素进行操作 while(levelLength > 0) { first = q.front(); q.pop(); if(first->lchild)q.push(first->lchild); if(first->rchild)q.push(first->rchild); if(--levelLength == 0)break; second = q.front();//第二个元素不需要出队 first->pNext = second; } } } void printLevel(BinaryTreeNode* root)//打印测试 { if(root) { cout << root->data << " pNext 为:"; if(root->pNext) cout << root->pNext->data << " " << endl; else cout << " NULL"<<endl; printLevel(root->lchild); printLevel(root->rchild); } } int main() { BinaryTreeNode* root = new BinaryTreeNode(1); root -> lchild = new BinaryTreeNode(2); root -> rchild = new BinaryTreeNode(3); root -> lchild -> lchild = new BinaryTreeNode(4); root -> lchild -> rchild = new BinaryTreeNode(5); root -> rchild -> lchild = new BinaryTreeNode(6); root -> rchild -> rchild = new BinaryTreeNode(7); root -> lchild -> lchild -> lchild = new BinaryTreeNode(8); addNextPoint(root); printLevel(root); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。