Leetcode:populating_next_right_pointers_in_each_node題解

Leetcode:populating_next_right_pointers_in_each_node題解

一、 題目

對於結構體:struct TreeLinkNode {

TreeLinkNode *left;

TreeLinkNode *right;

TreeLinkNode *next;

}

填充所有的結點如果存在右側的節點，則指上(next)右節點；如果沒有右側的節點，那麼就指上NULL，最初都指上NULL。

提示:只能使用給定的空間，並且你可以認為給定的二叉樹是一個完美的二叉樹。

例如：

1

/ \

2 3

/ \ \

4 5 7

處理後:

1 -> NULL

/ \

2 -> 3 -> NULL

/ \ \

4-> 5 -> 7 -> NULL

二、 分析

1、 空節點就直接返回

2、 左節點非空則連接右節點

3、 子節點連接兄弟節點的子節點，則root.right.next = root.next.left;

/**
 * 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==NULL) return;
        if(root->left!=NULL) root->left->next=root->right;
        if(root->right!=NULL&&root->next!=NULL)
        	root->right->next=root->next->left;
        	
        connect(root->left);
        connect(root->right);
    }
};


BFS
/**
 * 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) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        //breadth-first traversal
        queue bfsq;
        int levelCnt=0;
        int level2=0;
        
        if(root==NULL) return;
        bfsq.push(root);
        levelCnt++;
        TreeLinkNode *prevList=NULL;
        TreeLinkNode *topS=NULL;
        
        while(!bfsq.empty()) 
        {
            topS=bfsq.front();
            bfsq.pop();
            levelCnt--;
        
            if(topS->left!=NULL && topS->right!=NULL)
            {   
                bfsq.push(topS->left);
                level2++;
                bfsq.push(topS->right);
                level2++;
            }
            
            if(prevList!=NULL)
                prevList->next=topS;
            prevList=topS;
            
            if(levelCnt==0)
            {
                levelCnt=level2;
                level2=0;
                prevList=NULL;
            }
            
        }
    }
};