使用层次遍历初始化二叉树
时间: 2023-10-24 11:11:21 浏览: 37
层次遍历(又称广度优先遍历)是一种按照树的层次顺序依次遍历每个节点的方法。通过层次遍历,我们可以按照先后顺序依次访问每个节点,从而实现对二叉树的初始化。
下面是使用层次遍历初始化二叉树的具体步骤:
1. 定义一个队列,将根节点入队。
2. 当队列不为空时,进行如下操作:
a. 将队首节点出队,并将该节点的值保存到二叉树中。
b. 如果该节点有左子节点,将左子节点入队。
c. 如果该节点有右子节点,将右子节点入队。
3. 遍历结束后,二叉树的初始化就完成了。
示例代码如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def createTreeByLevelOrder(lst):
if not lst:
return None
root = TreeNode(lst[0])
queue = [root]
i = 1
while queue:
node = queue.pop(0)
if i < len(lst) and lst[i] is not None:
node.left = TreeNode(lst[i])
queue.append(node.left)
i += 1
if i < len(lst) and lst[i] is not None:
node.right = TreeNode(lst[i])
queue.append(node.right)
i += 1
return root
```
这里的 `lst` 是一个列表,其中存储了二叉树的节点值。列表中的 None 表示该节点为空。例如,列表 `[1,2,3,None,4,None,5]` 表示如下二叉树:
```
1
/ \
2 3
\ \
4 5
```