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:
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
Tree Depth-first Search
class Solution { public: TreeLinkNode* findLeftMostOfNextLayer(TreeLinkNode * root) { if(root == NULL) return NULL; if(root->left) return root->left; if(root->right) return root->right; return findLeftMostOfNextLayer(root->next); } void connect(TreeLinkNode *root) { if(root == NULL) return; TreeLinkNode* curLayer = root;//the leftmost node of the layer while(curLayer) { TreeLinkNode* curNode = curLayer ; while(curNode) { TreeLinkNode* left = curNode->left; TreeLinkNode* right= curNode->right; TreeLinkNode* next = findLeftMostOfNextLayer(curNode->next); //curNode is not a leaf node if(left && right) { left->next = right; } if(next) { if(right) right->next = next; else if(left) left->next = next; } curNode = curNode->next; } curLayer = findLeftMostOfNextLayer(curLayer); } } };
[LeetCode] Populating Next Right Pointers in Each Node II
原文：http://www.cnblogs.com/diegodu/p/4415177.html