1 题目

填充每个节点指向最右节点的next指针, 

填充所有节点的next指针，指向最接近它的同一层右边节点。如果没有同一层没有右边的节点，则应该将next指针设置为NULL。

初始时，所有的next指针都为NULL

注意：

你只能使用常量级的额外内存空间可以假设给出的二叉树是一个完美的二叉树(即，所有叶子节点都位于同一层，而且每个父节点都有两个孩子节点)。

2 解法

因为此题为按层来填充每一个节点的next为其同层的右节点(如果存在的话)

2.1 用队列的方法

2.2 不用队列

因为需要将每一层用next指针链接好, 所以遍历的思想是,链接好的一层遍历的时候把其下一层链接好, 在每一层遍历时,因为要链接其下一层的各个节点,所以要用一个last指针将上一个被链接为next的节点标记好,且要标记好下一层的头节点,以便于上一层遍历完遍历下一层,所以有:

/** * Definition for binary tree with next pointer. * struct TreeLinkNode { * int val; * TreeLinkNode *left, *right, *next; * TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {} * }; */ class Solution { public: void connect(TreeLinkNode *root) { TreeLinkNode *start(root); while (start) { TreeLinkNode *nextStart(NULL), *last(NULL); for (auto p = start; p != NULL; p = p->next) { if (p->left) { if (!nextStart) nextStart = p->left; if (last) last->next = p->left; last = p->left; } if (p->right) { if (!nextStart) nextStart = p->right; if (last) last->next = p->right; last = p->right; } } start = nextStart; } } };