首页 > 代码库 > [C++]LeetCode: 124 Populating Next Right Pointers in Each Node II(链接二叉树)

[C++]LeetCode: 124 Populating Next Right Pointers in Each Node II(链接二叉树)

2024-11-17 07:34:02   202人阅读

题目：

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

思路：这次我们要链接的不是完全二叉树，题目依然要求我们使用常数空间复杂度。我们需要多维护两个变量，总共四个变量。

  • lasthead : 维护上一层的链表的开始的节点；
  • pre: 维护当前节点的前一个有效节点，一直移动
  • curhead: 维护当前层的链表的开始的节点，每一层开始的节点不确定。我们需要在遍历该层时，将第一个非空的节点赋给curhead.
  • lastCur: 表示上一层的根结点，从上一层链表开始的节点开始,然后移动到同层的下一个节点。
我们需要在判断队列时，首先判断他的左右孩子结点是否存在，接下来还要判断curhead是否存在，然后通过pre连接节点，还有设置curhead. 在一层遍历完之后，我们将curhead赋给lasthead， 然后重置curhead = NULL. 直到最底层结束。
这道题也可以用于特殊情况，完全二叉树的解决：Populating Next Right Pointers in Each Node

复杂度：时间O(N), 空间O(1)
Attention:
1. 在理解了实现的过程后，我们要注意细节的实现。别忘了重置curhead.
lasthead = curhead;    //移动到下一层
curhead = NULL;        //重置curhead;

AC Code:
/**
 * 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;
        TreeLinkNode* lasthead = root;  //维护上一层的链表开始的节点
        TreeLinkNode* pre = NULL; //维护前一个结点
        TreeLinkNode* curhead = NULL; //维护当前层的链表开始的节点
        
        while(lasthead)
        {
            TreeLinkNode* lastCur = lasthead;   //lastcur从上一层链表的开始节点开始
            while(lastCur)
            {
                if(lastCur->left)
                {
                    if(curhead == NULL)
                    {
                        curhead = lastCur->left;  //如果还没确定该行的头结点，在碰到第一个非空节点时确定
                        pre = curhead;
                    }
                    else
                    {
                        pre->next = lastCur->left;
                        pre = pre->next;
                    }
                }
                
                if(lastCur->right)
                {
                    if(curhead == NULL)
                    {
                        curhead = lastCur->right;
                        pre = curhead;
                    }
                    else
                    {
                        pre->next = lastCur->right;
                        pre = pre->next;
                    }
                }
                lastCur = lastCur->next; //移动到下一个节点
            }
            
            lasthead = curhead;    //移动到下一层
            curhead = NULL;        //重置curhead;
        }
    }
};



[C++]LeetCode: 124 Populating Next Right Pointers in Each Node II(链接二叉树)


联系
我们