0116.md

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).

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
    

思路

  思路 1:

  根据题意每一个输入的数均为perfect binary tree 所以第n层的数的结点个数为2^n(根节点为0层)。记当前层的结点个数num，使用bfs对当前层的 前num-1个结点做处理分别指向下一个结点，最后一个结点值为null。每一个结点检测左右检点是否空，不为空则加入左右孩子结点到bfs使用的queue中。

  思路2:

  对于root结点，root->next = nullptr。对于树中的任意一个结点node，如果为空则结束。如果node->left!=nullptr,表示存在孩子结点则 node->left->next = node->right,而且 如果当前结点node->next不为空，则node->right = node->next->left,否则node->right = nullptr。

递归处理node->left和node->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) {
        queue<TreeLinkNode*> q;
        if(root) q.push(root);
        long level_num = 1;
        while(!q.empty()){
            TreeLinkNode* cur_ptr = q.front();
            q.pop();
            long temp_level_num = level_num;
            if(cur_ptr->left) q.push(cur_ptr->left);
            if(cur_ptr->right) q.push(cur_ptr->right);
            while(--temp_level_num){
                TreeLinkNode* next_ptr = q.front();
                q.pop();
                cur_ptr->next = next_ptr;
                cur_ptr = next_ptr;
                if(cur_ptr->left) q.push(cur_ptr->left);
                if(cur_ptr->right) q.push(cur_ptr->right);
            }
            cur_ptr->next = nullptr;
            level_num *=2;
        }
        
    }
};

递归

/**
 * 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;
        root->next = nullptr;
        cnn(root);
    }
    void cnn(TreeLinkNode* node){
        if(!node) return;
        
        if(node->left){
            node->left->next = node->right;
            if(node->next) node->right->next = node->next->left;
            else node->right->next = nullptr;
        }
        
        cnn(node->left);
        cnn(node->right);
    }
};