OJ-leetcode-117. 填充每个节点的下一个右侧节点指针II(中等二叉树)

短命女 2022-12-11 03:23 71阅读 0赞

**目录**

题目

思路1

代码

结果

思路2

代码

结果

优秀题解

提升笔记

--------------------

# 题目 #

给定一个二叉树

struct Node \{  
  int val;  
  Node \*left;  
  Node \*right;  
  Node \*next;  
\}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

进阶：

你只能使用常量级额外空间。  
    使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例：

![a5d95fc158b54c265e39bd7e6183494d.png][]

输入：root = \[1,2,3,4,5,null,7\]  
输出：\[1,\#,2,3,\#,4,5,7,\#\]  
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

提示：

树中的节点数小于 6000  
    -100 <= node.val <= 100

链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii

通过读题可以明确，大致有三种思路，空间复杂度为O(n)级、递归解题、空间复杂度O(1)级。O(n)级应该是层次遍历，官方应该是希望我们使用递归并且空间复杂度O(1)。

1 2 4 -1 -1 5 -1 -1 3 -1 7 -1 -1

# 思路1 #

## 代码 ##

// 思路1 层次遍历
    	Node* connect(Node* root) {
    		if (!root)return nullptr;
    		queue<Node*> q;
    		Node* front;
    		q.emplace(root);
    		while (!q.empty())
    		{
    			int n = q.size();
    			//cout << "本层元素个数:"<<n<<endl;
    			Node* left = nullptr;//同一层左侧节点
    			//连接同层的next
    			for (int i = 0; i < n; ++i)
    			{	
    				front = q.front();
    				q.pop();
    				if (front->left) q.emplace(front->left);
    				if (front->right)q.emplace(front->right);
    				if (0 != i)
    				{
    					left->next = front;
    					//cout << left->val << "与" << front->val << "已连接" << endl;
    				}
    				left = front;	
    			}
    		}
    		return root;
    	}

## 结果 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70][] 结果

# 思路2 #

利用next遍历本层，不使用队列，遍历本层时将下一层使用next连接，并记录下一层头结点head

本层遍历结束后，转到下一层的head节点继续遍历，直到head为空

一层遍历时流程图如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1][] 一层的遍历流程图

## 代码 ##

class Solution {
    public:
    	Node* connect(Node* root) {
    		if (!root)return nullptr;
    		Node* level = root;  //当前层节点
    		Node* head = nullptr;//下一层的头结点，用于转到下一层
    		Node* lastNext = nullptr;// 上一个next
    		// 使用next遍历当前层，将下一层使用next连起来
    		while (level)
    		{
    			//cout << "本层:" <<level->val<< endl;
    			// 若有左孩子，连接一下
    			if (level->left)
    			{
    				// 本层头结点已定
    				if (head)
    				{ 
    					lastNext->next = level->left;
    					//cout << lastNext->val << "连接" << level->left->val << endl;
    					lastNext = lastNext->next;
    				}
    				// 本层头结点未定 level为本层第一个节点且有左孩子
    				else { 
    					head = level->left;
    					//cout << "下一层头结点" << head->val << endl;
    					lastNext = level->left; 
    				}
    			}
    			//若有右孩子，连接一下
    			if(level->right)
    			{
    				// 本层头结点已定
    				if (head)
    				{
    					lastNext->next = level->right; 
    					//cout << lastNext->val << "连接" << level->right->val << endl;
    					lastNext = lastNext->next;
    				}
    				// 本层头结点未定 level为本层第一个节点且有右孩子
    				else {
    					head = level->right;
    					//cout << "下一层头结点" << head->val << endl;
    					lastNext = level->right;
    				}
    			}
    			// 本层没结束
    			if(level->next)level = level->next;
    			// 本层已结束 转至本层头结点的孩子 若左右孩子均为空，level为空，结束
    			else
    			{
                                    if(!head)break;
    				level = head;
    				//cout << "转至" <<level->val<<"层"<< endl;
    				// 重置下一层的头结点
    				head = nullptr;
    			}
    		}
    		return root;
    	}
    };

## 结果 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 2][] 结果截图

# 优秀题解 #

[简洁递归][Link 1]

class Solution {
    public:
        Node* connect(Node* root) {
            if(root and (root->left or root->right)){
                if(root->left and root->right) root->left->next = root->right;
                
                Node *node = root->right ? root->right : root->left;
                Node *head = root->next;
                while (head and not (head->left or head->right)){
                    head = head->next;
                }
                node->next = head ? (head->left ? head->left : head->right) : nullptr;
                
                connect(root->right);
                connect(root->left);
            }
            return root;
        }
    };

# 提升笔记 #

1. 利用已有的next

更多内容：[OJ网站题目分类，分难度整理笔记（leetcode、牛客网）][OJ_leetcode]

喜欢本文的请动动小手点个赞，收藏一下，有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[a5d95fc158b54c265e39bd7e6183494d.png]: /images/20221123/2494f66b3b3c45f6a46c36f0da1d31f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70]: /images/20221123/7eb5757e31a14fdfad76e377c4dfc4bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1]: /images/20221123/cf5a4976a6044abd92d44c2e33229b39.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 2]: /images/20221123/d28fc31eb02f4564a8a905962ee816bc.png
[Link 1]: https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/solution/c-o1kong-jian-jian-ji-di-gui-by-qqqun902025048/
[OJ_leetcode]: https://blog.csdn.net/lady_killer9/article/details/108273799