欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【C语言 LeetCode 116】填充每个节点的下一个右侧节点指针

程序员文章站 2022-05-20 21:32:16
...

广度优先搜索(层次遍历)解决填充每个节点的下一个右侧节点指针

  • 题目

给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

struct Node {
	int val;
    struct Node *left;
    struct Node *right;
    struct Node *next;
};

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。

  • 思路

采用层次遍历依次遍历每一层,当不是该层最后一个结点,将next指针连接到下一个结点;是最后一个结点next指针置NULL。

  • 代码
#define max 2500

struct Node* connect(struct Node* root) 
{
    struct Node *que[max],*p;
    int rear=0, front=0, last=1;
    if(root)
    {
        que[rear]=root;
        rear = (rear+1)%max;
        while(rear!=front)
        {
            p=que[front];
            front = (front+1)%max;
            if(p->left)
            {
                que[rear] = p->left;
                rear = (rear+1)%max;
            }
            if(p->right)
            {
                que[rear] = p->right;
                rear = (rear+1)%max;
            }
            if(last == front)	//判断是否为该层最后一个结点
            {
                p->next = NULL;
                last = rear;
            }
            else
                p->next = que[front];	//连接下一个右侧结点
        }
    }
    return root;
}