leetcode:Populating Next Right Pointers in Each Node

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  7
      

After calling your function, the tree should look like:

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

Hide Tags   Tree Depth-first Search

題目位址：https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node/

解題思路：

這道題的第一個解法是自己解出來的，還是挺開心的，畢竟還是個難度系數是medium的題呢哈哈^_^

第一種解法：利用二叉樹層序周遊的思想，先按層序周遊的順序把每個節點連起來。然後把每一層的最右的節點的next都指向NULL（因為是滿二叉樹，是以直接root->right。。。到底就行了）

代碼：

/**
 * 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) {
        //可以采用層序周遊的方法把所有結點按層序周遊的順序連接配接
        //然後把所有的最右結點的next置為null
        if(root == NULL) return;
        queue<TreeLinkNode *> Q;
        
        Q.push(root);
        while(!Q.empty()){
            TreeLinkNode *cur = Q.front();
            Q.pop();
            
            if(!Q.empty()) cur->next = Q.front();
            if(cur->left) Q.push(cur->left);
            if(cur->right) Q.push(cur->right);
        }
        
        TreeLinkNode *p = root;
        while(p){
            p->next = NULL;
            p = p->right;
        }
    }
};
           

第二種解法：這種方法參考了别人的答案，因為二叉樹層序周遊的解法還是需要一些空間複雜度，而這裡題目要求要用常數空間複雜度。是以用遞歸的解法。

代碼：

/**
 * 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){
            root->left->next = root->right;
        }
        //如果右節點非空就将右節點的next連接配接到...結合上圖的5,6節點看
        if(root->right && root->next){
            root->right->next = root->next->left;
        }
        
        connect(root->left);
        connect(root->right);
    }
};