赞
踩
给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
示例:
输入:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
输出:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。
提示:
你只能使用常量级额外空间。
使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
方法1:利用next结点
""" # 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 leftmost = root while leftmost.left: head = leftmost while head: //connect the first level head.left.next = head.right //connect the second level if head.next: head.right.next = head.next.left head = head.next leftmost = leftmost.left return root
/** * Definition for a Node. * struct Node { * int val; * struct Node *left; * struct Node *right; * struct Node *next; * }; */ struct Node* connect(struct Node* root) { if (!root) { return root; } struct Node *leftmost = root; struct Node *head = leftmost; while (leftmost->left) { head = leftmost; while (head) { //connect the first level head->left->next = head->right; //connect the second level if (head->next) { head->right->next = head->next->left; } head = head->next; } leftmost = leftmost->left; } return root; }
二,层次遍历
""" # 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 ans = list() right, left = 0, 0 ans.append(root) right += 1 while left < right: levelSize = right - left for i in range(levelSize): node = ans[left] left += 1 if i < levelSize - 1: node.next = ans[left] if node.left: ans.append(node.left) right += 1 if node.right: ans.append(node.right) right += 1 return root
/** * Definition for a Node. * struct Node { * int val; * struct Node *left; * struct Node *right; * struct Node *next; * }; */ struct Node* connect(struct Node* root) { if (!root) { return root; } struct Node *queue[5001]; int left = 0, right = 0; queue[right++] = root; while (left < right) { int levelSize = right - left; for (int i = 0; i < levelSize; i++) { struct Node *node = queue[left++]; if (i < levelSize - 1) { node->next = queue[left]; } if (node->left != NULL) { queue[right++] = node->left; } if (node->right != NULL) { queue[right++] = node->right; } } } return root; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。