如何将一棵二叉树转化为森林?
时间: 2024-01-19 17:04:32 浏览: 32
将一棵二叉树转化为森林的步骤如下:
1. 如果根节点只有左孩子,将其左孩子作为一棵树,断开根节点与左孩子的连线。
2. 如果根节点只有右孩子,将其右孩子作为一棵树,断开根节点与右孩子的连线。
3. 如果根节点既有左孩子又有右孩子,将其左孩子作为一棵树,断开根节点与左孩子的连线,将其右孩子作为一棵树,断开根节点与右孩子的连线。
4. 对于每个生成的树,将其根节点与其右孩子断开连线,然后按照二叉树转树的方法将其转化为树。
代码示例:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def binaryTreeToForest(root: TreeNode) -> List[TreeNode]:
res = []
if not root:
return res
if not root.left and not root.right:
res.append(root)
return res
if root.left:
left = root.left
root.left = None
res += binaryTreeToForest(left)
if root.right:
right = root.right
root.right = None
res += binaryTreeToForest(right)
res.append(root)
return res
```