[LeetCode]Populating Next Right Pointers in Each Node II

和I不一样，这道题不限定是perfect binary tree了，所以我们不能用递归。那么我们就得转而用层序遍历的方法，我们把当前层的子节点连起来，然后去下一层，以此类推。时间复杂度O(n)，常数空间，代码如下：

	/**
	* 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;
	auto curr = root;
	while(curr)
	{
	curr = findNext(curr);
	if(!curr)break;
	TreeLinkNode* head = curr->left? curr->left: curr->right;
	while(curr)
	{
	if(curr->left && curr->right)
	curr->left->next = curr->right;
	TreeLinkNode* next = findNext(curr->next);
	if(!next)break;
	if(curr->right)curr->right->next = next->left? next->left: next->right;
	else curr->left->next = next->left? next->left: next->right;
	curr = next;
	}
	curr = head;
	}
	}
	private:
	TreeLinkNode* findNext(TreeLinkNode* curr)
	{
	while(curr)
	{
	if(curr->left || curr->right)
	return curr;
	curr = curr->next;
	}
	return curr;
	}
	};

view raw Populating Next Right Pointers in Each Node II.cpp hosted with ❤ by GitHub