LeetCode 117 Populating Next Right Pointers in Each Node II

LeetCode 117

Populating Next Right Pointers in Each Node II

• Problem Description：

  对于给定的二叉树的任意节点，如果不是所在层的最右节点，则其next指针指向其右侧节点；如果是所在层的最右节点，则其next指针指向NULL。

  具体的题目信息：

  https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/description/

• Example:

  

• Solution:
  • 解题思路：用

    pre

    指向第一次访问的节点，用

    cur

    指向第二次访问的节点，如果这两个指针同时存在，用

    pre->next = cur

    将两个节点横向连接起来，并移动指针使得

    pre = cur, cur = NULL

    。
  • 编程实现：

/**
 * 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) {
        if (root == NULL) return;
        int front = -, rear = -;
        int last = ;
        TreeLinkNode* node[];
        node[++rear] = root;
        TreeLinkNode* p;
        TreeLinkNode* pre = NULL;
        TreeLinkNode* cur = NULL;
        while(front < rear) {
            p = node[++front];
            if (pre == NULL) {
                pre = p;
            } else {
                cur = p;
            }
            if (p->left) {
                node[++rear] = p->left;
            }
            if (p->right) {
                node[++rear] = p->right;
            }
            if (cur != NULL) {
                pre->next = cur;
                pre = cur;
                cur = NULL;
            }
            if (front == last) {
                pre->next = cur;
                pre = NULL;
                last = rear;
            }
        }
    }
};
           

• 一点疑惑：不知道为什么这道题目Leetcode上没有

  Run Code

  的编译按钮，而且Leetcode的debug环境好像有点问题，在调试过程中一直报编译错误但是提交之后却accept了。