LeetCode-117. Populating Next Right Pointers in Each Node II

LeetCode-117. Populating Next Right Pointers in Each Node II

Given a binary tree

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:

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":null,"next":null,"right":{"$id":"6","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":null,"right":null,"val":7},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"6","left":null,"next":null,"right":{"$ref":"5"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"6"},"val":1}Explanation: Given the above 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.

题解：

class Solution {public: Node* connect(Node* root) { if (root == NULL) { return root; } queue q; q.push(root); int n = 1; int num = 0; while (q.empty() == false) { Node *t = q.front(); q.pop(); n--; if (t != NULL) { if (n == 0) { t->next = NULL; } else { t->next = q.front(); } if (t->left != NULL) { q.push(t->left); num++; } if (t->right != NULL) { q.push(t->right); num++; } } if (n == 0) { n = num; num = 0; } } return root; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。