Given a binary tree
struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *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.
Note:
You may only use constant extra space. You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children). For example, Given the following perfect binary tree,
1 / / 2 3 / / / / 4 5 6 7After calling your function, the tree should look like:
1 -> NULL / / 2 -> 3 -> NULL / / / /4->5->6->7 -> NULLs思路： 1. 還是樹。變化是：除了縱向的遍歷樹，現在還要增加功能，使其可以橫向遍歷。 2. 初略觀察有兩種pattern：一種是，2的next指向就是2的parent的child 3;另一種，5的next是5的parent的next 3的child?；蛘卟灰欢ㄟ@么看，問題的另一面是：2的左孩子的next是2的右孩子；2的右孩子的next是2的next的左孩子。也是兩種情況，不同的是，一種從下往上看，所以每個node都借助parent;一種是從上往下看，所以每個node都借組child。由于是樹，找孩子容易，找父母難。自然我們選擇用第二個思路，不過兩個思路都是一個思路的兩個角度。 3. 上面的思路也就意味著
//方法1： recursive.先處理root,然后左，最后右。in-orderclass Solution {public: void connect(TreeLinkNode *root) { // if(!root) return; if(!root->left&&!root->right) return; root->left->next=root->right; if(root->next) root->right->next=root->next->left; connect(root->left); connect(root->right); }};//方法2： iterative.不用queue,也不用stack.單用雙重循環就夠了，一個從上往下，一個從左往右class Solution {public: void connect(TreeLinkNode *root) { // TreeLinkNode* horizon=NULL,*vertical=root; while(vertical&&vertical->left){ horizon=vertical; while(horizon){ if(horizon->left) horizon->left->next=horizon->right; if(horizon->next) horizon->right->next=horizon->next->left; horizon=horizon->next; } vertical=vertical->left; } }};新聞熱點
疑難解答
