本文共 2700 字，大约阅读时间需要 9 分钟。

题目

给定一个二叉树

struct Node {

int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

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

思路

从上一题完美二叉树进一步，需要额外判断各个子节点存在与否，再选择如何给next赋值。

初步的想法是在完美二叉树的代码基础上，通过if语句的判断利用递归实现问题。发现代码书写过于复杂，而且没有想到使用next==nullptr去纵向判断。参考解析，着重记录下代码写法，使用三目运算符和逻辑操作符简洁的进行表示：

class Solution {   public:    Node* connect(Node* root) {           if(root and (root->left or root->right)){   //root节点存在且至少存在一个子节点。            //两个子节点同时存在时，可以直接给next赋值            if(root->left and root->right) root->left->next = root->right;            //需要两个父节点之间的子节点进行next操作，优先为right，不存在咋为left(right和left至少存在一个)            //学习利用三目运算符用简洁的代码 表示带判断后的选择！！！！！！！！！！！            Node *node = root->right ? root->right : root->left;            //要进行父节点下的子节点next操作，需保证root->next至少存在子节点            //初始化需要操作的父节点，即找到存在子节点的父节点进行next操作            Node *head = root->next;            while (head and not (head->left or head->right)){   //root->next存在，但是没子节点时继续指向下一个next                head = head->next;//保证head是同一层中存在子节点的同级节点，没有则 为nullptr且退出循环            }            //对子节点进行next操作，首先需确保有两个父节点，有的话在判断是父节点的哪个左右子节点（若都不存在则为nullptr），双重三目运算符            node->next = head ? (head->left ? head->left : head->right) : nullptr;            //先对右子节点进行next操作            connect(root->right);            connect(root->left);        }        return root;    }};

借此题，重温下递归的操作：

明白一个函数的作用并相信它能完成这个任务，千万不要试图跳进细节！ 递归的思想是某个函数直接或间接地调用自身，这样把原问题的求解转换成很多性质相同但是规模更小的子问题上。需要关注如何把原问题划分为 两个特征：结束条件和自我调用 结束条件：在本题中当父节点不存在或者父节点无子节点则会挨个退出。 自我调用：传递子问题。

想不到用嵌套的三目运算符，可以通过if来判断：

class Solution {   public:    Node* connect(Node* root) {           connect(root, nullptr);        return root;    }    void connect(Node* root, Node* next) {           if (root == nullptr) {               return;        }        root->next = next;        Node* p = nullptr;        if(root->right != nullptr){               p = root->next;            while(p != nullptr){                   if(p->left != nullptr){                       p = p->left;                    break;                }                if(p->right != nullptr){                       p = p->right;                    break;                }                p = p->next;            }            connect(root->right, p);            connect(root->left, root->right);        }else{               p = root-> next;            while(p != nullptr){                   if(p->left != nullptr){                       p = p->left;                    break;                }                if(p->right != nullptr){                       p = p->right;                    break;                }                p = p->next;            }            connect(root->left, p);        }    }};