leetcode_116. 填充每个节点的下一个右侧节点指针

目录

一、题目内容

二、解题思路

三、代码


一、题目内容

给定一个二叉树

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 所示。

提示:

你只能使用常量级额外空间。

使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。

二、解题思路

利用队列,每次出队第一个节点,然后在尾部添加左右节点,除了最后一个出队元素next为None,之前的节点的next都指向出队之后的queue中的第一个元素(右侧节点)。

三、代码


  
  1. """
  2. # Definition for a Node.
  3. """
  4. class Node:
  5. def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
  6. self.val = val
  7. self.left = left
  8. self.right = right
  9. self.next = next
  10. def __repr__(self):
  11. return str(self.val)
  12. class Solution:
  13. def connect(self, root: 'Node') -> 'Node':
  14. if not root:
  15. return None
  16. queue = [root]
  17. while queue:
  18. l = len(queue)
  19. for i in range(l):
  20. q = queue.pop(0)
  21. if q.left:
  22. queue.append(q.left)
  23. if q.right:
  24. queue.append(q.right)
  25. if i < l - 1:
  26. q.next = queue[0]
  27. return root
  28. if __name__ == '__main__':
  29. a = Node(1)
  30. a.left = Node(2)
  31. a.right = Node(3)
  32. a.left.left = Node(4)
  33. a.left.right = Node(5)
  34. a.right.right = Node(7)
  35. s = Solution()
  36. ans = s.connect(a)
  37. print(ans)

文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。

原文链接:nickhuang1996.blog.csdn.net/article/details/109094968

(完)