专栏首页米扑专栏【leetcode】Populating Next Right Pointers in Each Node II

【leetcode】Populating Next Right Pointers in Each Node II

Question:

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:

  • You may only use constant extra space.

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

Anwser 1:

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(NULL == root){
            return;
        }

        TreeLinkNode *cur = root->next;
        TreeLinkNode *p = NULL;
        
        while(cur != NULL){     // find last right node (left or right)
            if(cur->left) {
                p = cur->left;
                break;
            }
            if(cur->right){
                p = cur->right;
                break;
            }
            cur = cur->next;
        }
        
        if(root->right){
            root->right->next = p;
        }
        
        if(root->left){
            root->left->next = root->right ? root->right : p;
        }
        
        connect(root->right);   // from right to left
        connect(root->left);
    }
};

注意点:

1) list为非完美二叉树,右分支可能为空,因此从right -> left 遍历

2) 从最右分支开始查找,且root没有 left 节点,则找 right 节点

Anwser 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(NULL == root){
            return;
        }
        
        queue<TreeLinkNode *> Q;    // save one line root(s)
        queue<TreeLinkNode *> Q2;   // save next one line root(s), swap with Q
        Q.push(root);
        
        while(!Q.empty()){
            TreeLinkNode *tmp = Q.front();
            Q.pop();
            
            if(tmp->left) Q2.push(tmp->left);
            if(tmp->right) Q2.push(tmp->right);
            
            if(Q.empty()){
                tmp->next = NULL;
                queue<TreeLinkNode*> tmpQ = Q;  // swap queue
                Q = Q2;
                Q2 = tmpQ;
            } else {
                tmp->next = Q.front();
            }
        }
    }
};

注意点:

1) 新增一个Q2队列,保存下一行的全部元素,辅助判断是最后一个元素(Q为空)则置为NULL

2) queue队列实现比递归要好

Anwser 3: 

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(NULL == root){
            return;
        }
        
        queue<TreeLinkNode *> Q;    // save one line root(s)
        Q.push(root);
        Q.push(NULL);       // flag
        
        while(!Q.empty()){
            TreeLinkNode *tmp = Q.front();
            Q.pop();
            
            if(tmp != NULL){        // check flag
                if(tmp->left) Q.push(tmp->left);
                if(tmp->right) Q.push(tmp->right);
                tmp->next = Q.front();
            } else {        
                if(Q.empty()){      // pop flag = NULL, then check is empty
                    break;
                }
               Q.push(NULL);
            }
        }
    }
};

注意点:

对比第二种方法,改进点是每一行结束处,采用NULL作为标志位

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode】Populating Next Right Pointers in Each Node

    Populate each next pointer to point to its next right node. If there is no next ...

    阳光岛主
  • 【leetcode】Path Sum

    Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc...

    阳光岛主
  • 【leetcode】Minimum Depth of Binary Tree

    Given a binary tree, find its minimum depth.

    阳光岛主
  • Leetcode 116 Populating Next Right Pointers in Each Node

    Given a binary tree struct TreeLinkNode { TreeLinkNode *left; T...

    triplebee
  • 【leetcode】Populating Next Right Pointers in Each Node

    Populate each next pointer to point to its next right node. If there is no next ...

    阳光岛主
  • LeetCode 129 Sum Root to Leaf Numbers

    ShenduCC
  • LeetCode 257. Binary Tree Paths

    ShenduCC
  • Populating Next Right Pointers in Each Node

    问题:将二叉树的所有结点指向他的右边的一个结点 分析:对于每一个结点来说,其操作都是一样的,除了他的左儿子指向右儿子外,其左儿子的全部右后辈均指向其右儿子的全部...

    用户1624346
  • 【leetcode】Minimum Depth of Binary Tree

    Given a binary tree, find its minimum depth.

    阳光岛主
  • Centos7 下安装 RabbitMQ

    其中APPLICATIONS DISABLED 标示是必须要安装的,另外两个项目可以忽略 jinterface : Java compiler disable...

    海向

扫码关注云+社区

领取腾讯云代金券