首页 > 代码库 > 给定一颗完全二叉树,给每一层添加上next的指针,从左边指向右边

给定一颗完全二叉树,给每一层添加上next的指针,从左边指向右边

给你机会发出声音,但是不给你机会证明高层的决定是错的

RT: 时间复杂度O(n) 空间复杂度O(1)

 原理就是有指针指向父节点和当前的节点,左孩子必指向右孩子,右孩子必指向父节点的下一个节点的左孩子 
 
void Solution::yahooTree(TreeNode *root){    if (root == NULL)        return;    TreeNode *p = root;    root->next = NULL;    TreeNode *tmp = root->left;    while(p){        if (p->right!=NULL){            if (p->next!=NULL){                p->right->next = NULL;                p->left->next = p->right;            }else{                p->right->next = p->next->left;                p->left->next = p->right;            }        }else if (p->left!=NULL){            p->left->right = NULL;        }        p = p->next;        if (p == NULL){            if (tmp!=NULL)){                p = tmp;                tmp = tmp->left;            }else{                return ;            }        }    }}

 

给定一颗完全二叉树,给每一层添加上next的指针,从左边指向右边