题目
给定一个二叉树
struct Node { int val; Node *left; Node *right; Node *next; }
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入：root = [1,2,3,4,5,null,7] 输出：[1,#,2,3,#,4,5,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
解题
方法一：层序遍历
python解法
和LC-116一致的方法，只是需要注意，这里不再是完美二叉树了，于是要对left和right分别判断存在，才能加入到队列中。
""" # Definition for a Node. class Node: def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None): self.val = val self.left = left self.right = right self.next = next """ class Solution: def connect(self, root: 'Node') -> 'Node': if not root: return root queue = [root] while queue: l = len(queue) for i in range(l): cur = queue.pop(0) left,right = cur.left,cur.right if i==l-1: cur.next=None else: cur.next=queue[0] if left: queue.append(left) if right: queue.append(right) return root
c++解法
/* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node* next; Node() : val(0), left(NULL), right(NULL), next(NULL) {} Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {} Node(int _val, Node* _left, Node* _right, Node* _next) : val(_val), left(_left), right(_right), next(_next) {} }; */ class Solution { public: Node* connect(Node* root) { if(!root) return nullptr; queue<Node*> queue; queue.push(root); while(!queue.empty()){ int l=queue.size(); for(int i=0;i<l;i++){ Node* cur=queue.front(); queue.pop(); if(i!=l-1){ cur->next=queue.front(); } if(cur->left){ queue.push(cur->left); } if(cur->right){ queue.push(cur->right); } } } return root; } };
方法二：O(1)空间的方法
python解法
""" # Definition for a Node. class Node: def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None): self.val = val self.left = left self.right = right self.next = next """ class Solution: def connect(self, root: 'Node') -> 'Node': if not root: return root rootNode = root first_next = None node_next = None while rootNode: if rootNode.left: if not first_next: first_next =rootNode.left if node_next: node_next.next = rootNode.left node_next = rootNode.left if rootNode.right: if not first_next: first_next =rootNode.right if node_next: node_next.next = rootNode.right node_next = rootNode.right rootNode = rootNode.next if not rootNode: rootNode=first_next first_next=None node_next=None return root
