博文中会简要介绍Leetcode P0116题目分析及解题思路。
“Populating Next Right Pointers in Each Node”是一道比较基础的题目，主要考察的就是层遍历，即BFS。
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.
Follow up:
You may only use constant extra space. Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.
以下是Java的题解代码实现。
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
if (root == null)
return root;
Queue<Node> queue = new LinkedList<>();
int numOfNodesInCurrLevel = 1, numOfNodesInNextLevel = 0;
queue.offer(root);
while (!queue.isEmpty()) {
Node curr = queue.poll();
if (curr.left != null) {
queue.offer(curr.left);
++numOfNodesInNextLevel;
}
if (curr.right != null) {
queue.offer(curr.right);
++numOfNodesInNextLevel;
}
--numOfNodesInCurrLevel;
if (numOfNodesInCurrLevel == 0) {
curr.next = null;
numOfNodesInCurrLevel = numOfNodesInNextLevel;
numOfNodesInNextLevel = 0;
}
else
curr.next = queue.peek();
}
return root;
}
}
以下是C++的题解代码实现。
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
Node* connect(Node* root) {
if (!root)
return root;
queue<Node*> node_queue;
int curr_nodes = 1, next_nodes = 0;
node_queue.push(root);
while (!node_queue.empty()) {
Node *curr = node_queue.front();
node_queue.pop();
if (curr->left) {
++next_nodes;
node_queue.push(curr->left);
}
if (curr->right) {
++next_nodes;
node_queue.push(curr->right);
}
--curr_nodes;
if (curr_nodes == 0) {
curr->next = NULL;
curr_nodes = next_nodes;
next_nodes = 0;
}
else
curr->next = node_queue.front();
}
return root;
}
};