Leetcode Populating Next Right Pointers in Each Node II

Populating Next Right Pointers in Each Node II

 

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

  • You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /        2    3
     / \        4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /        2 -> 3 -> NULL
     / \        4-> 5 -> 7 -> NULL


如何处理各个细节的问题很重要,决定了能否写出更加简洁的程序来。

void connect(TreeLinkNode *root) 
	{
		while (root && !root->left && !root->right) root = root->next;
		if (root == NULL) return;
		
		TreeLinkNode *rightSibling;
		TreeLinkNode *p1 = root;
		while (p1) 
		{
			TreeLinkNode *p_next = p1->next;
			while (p_next && !p_next->left && !p_next->right) 
				p_next = p_next->next;

			if (p_next)
				rightSibling = p_next->left? p_next->left:p_next->right;
			else rightSibling = NULL;

			if (p1->left && p1->right)
			{
				p1->left->next = p1->right;
				p1->right->next = rightSibling;
			}
			else if (p1->right)
			{
				p1->right->next = rightSibling;
			}
			else
			{
				p1->left->next = rightSibling;
			}

			p1 = p_next;
		}
		if (root->left)
			connect(root->left);
		else if(root->right)
			connect(root->right);
	}

Leetcode论坛上的一个简洁的程序,写得太好了,编程功底就在微小的差别中体现出来了。

具体思想是和我上面的程序一样的。

//LeetCode论坛上的
	// the link of level(i) is the queue of level(i+1)
	void connect2(TreeLinkNode * n) {
		while (n) {
			TreeLinkNode * next = NULL; // the first node of next level
			TreeLinkNode * prev = NULL; // previous node on the same level
			for (; n; n=n->next) {
				if (!next) next = n->left?n->left:n->right;

				if (n->left) {
					if (prev) prev->next = n->left;
					prev = n->left;
				}
				if (n->right) {
					if (prev) prev->next = n->right;
					prev = n->right;
				}
			}
			n = next; // turn to next level
		}
	}





Leetcode Populating Next Right Pointers in Each Node II

上一篇:oracle 性能优化方向


下一篇:Windows Server 2008上MYSQL外网无法访问有关问题解决