您的位置: 首页  >  文章  >  [leetcode] 116. Populating Next Right Pointers in Each Node

[leetcode] 116. Populating Next Right Pointers in Each Node

分类: 文章 • 2023-11-29 18:27:34

Description

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

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

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example:[leetcode] 116. Populating Next Right Pointers in Each Node
Input:

{"$id":"1","left":{"$id":"2","left":
{"$id":"3","left":null,"next":null,"right":null,"val":4},
"next":null,"right":{"$id":"4","left":null,"next":null,"right":
null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":
{"$id":"6","left":null,"next":null,"right":null,"val":6},
"next":null,"right":{"$id":"7","left":null,"next":null,
"right":null,"val":7},"val":3},"val":1}

Output:

{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":
{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":
{"$id":"6","left":null,"next":null,"right":null,"val":7},
"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},
"next":{"$id":"7","left":{"$ref":"5"},"next":null,
"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},
"next":null,"right":{"$ref":"7"},"val":1}

Explanation:

Given the above perfect binary tree (Figure A), 
your function should populate each next pointer to point to
 its next right node, just like in Figure B.

Note:

  • You may only use constant extra space.
  • Recursive approach is fine, implicit stack space does not count as extra space for this problem.

分析

题目的意思是：给你一棵完全二叉树，把每个节点指向每一层的右节点，如果节点没有右节点，则置空。

  • 递归和非递归都可以做，非递归模拟的是栈，递归很简洁，需要手手工模拟一下，个人感觉不怎么好理解。

代码-递归

/**
 * 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){
            return;
        }
       if(root->left) root->left->next=root->right;
        if(root->right) root->right->next=root->next ? root->next->left:NULL;
        connect(root->left);
        connect(root->right);
    }
};

代码-非递归

/**
 * 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)
            return;
        TreeLinkNode *p=root,*q;
        while(p->left){
            q=p;
            while(q){
                q->left->next=q->right;
                if(q->next){
                    q->right->next=q->next->left;
                }
                q=q->next;
            }
            p=p->left;
        }
    }
};

参考文献

[编程题]populating-next-right-pointers-in-each-node
[LeetCode] Populating Next Right Pointers in Each Node 每个节点的右向指针

相关推荐