程序员社区

给定一颗完全二叉树,给每一层添加上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 ;
            }
        }
    }
}
复制代码

 

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 给定一颗完全二叉树,给每一层添加上next的指针,从左边指向右边

相关推荐

  • 暂无文章

一个分享Java & Python知识的社区