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

LeetCode 117 Populating Next Right Pointers in Each Node II

程序员文章站 2022-04-27 08:51:12
...

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:
    LeetCode 117 Populating Next Right Pointers in Each Node II
  • 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 = -1, rear = -1;
        int last = 0;
        TreeLinkNode* node[6000];
        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了。
相关标签: tree LevelOrder