leetcode-116 填充每个节点的下一个右侧节点指针

  • English:

leetcode-116 填充每个节点的下一个右侧节点指针

给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

1
2
3
4
5
6
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

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

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

实现递归方法将两个左右子树进行相连,递归即刻。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
# 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
self.connectwithtwonodes(root.left, root.right)
return root

def connectwithtwonodes(self, left, right):
if not left or not right:
return
left.next = right
self.connectwithtwonodes(left.left, left.right)
self.connectwithtwonodes(right.left, right.right)
self.connectwithtwonodes(left.right, right.left)
-------The end of this article  Thank you for your reading-------
  • 本文作者: Eree
  • 本文链接: https://ereebay.me/posts/15994/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!