[LeetCode] 117. Populating Next Right Pointers in Each Node II

轉自LeetCode

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

<Solution>

這題是 Populating Next Right Pointers in Each Node 的衍生題

差別在於，這次不再是 perfect binary tree 了

大方向還是level traversal，但因為題目有要求要 constant space

所以採用之前的第二種解法，並修正以下幾個點

• 需要使用三個指針，一個指向每個 level 第一個有 child node 的 node；一個指向目前正在處理的 root；一個指向目前需要找到 next 的 child node

• 每次都要找到第一個有 child node 的 node，並且以它開始處理，直到沒有 next。中間如果有遇到沒有 child node 的 root，就略過

code 如下

	/**
	* 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 *levelFirstNode = root;
	TreeLinkNode *currRoot, *currNode;
	while(levelFirstNode) {
	currRoot = levelFirstNode;
	//> find first root node which has child node
	while(currRoot && !currRoot->left && !currRoot->right) {
	currRoot = currRoot->next;
	}
	if(!currRoot) {
	return;
	}
	currNode = (currRoot->left) ? currRoot->left : currRoot->right;
	//> first node of next level
	levelFirstNode = currNode;
	//> link all node in the same level
	while(currRoot) {
	if(currNode == currRoot->left) {
	if(currRoot->right) {
	currNode->next = currRoot->right;
	currNode = currNode->next;
	}
	currRoot = currRoot->next;
	}
	else if(currNode == currRoot->right) {
	currRoot = currRoot->next;
	}
	else {
	if(!currRoot->left && !currRoot->right) {
	currRoot = currRoot->next;
	continue;
	}
	currNode->next = (currRoot->left) ? currRoot->left : currRoot->right;
	currNode = currNode->next;
	}
	}
	}
	}
	};

view raw binaryTreeToLinkedBinaryTreeII_1.cpp hosted with ❤ by GitHub