二叉树叶子结点到根结点的路径求解
时间: 2023-11-29 21:05:04 浏览: 128
二叉树叶子结点到根结点的路径求解可以使用递归的方式实现。具体步骤如下:
1. 如果当前节点为空,则返回空列表。
2. 如果当前节点是叶子节点,则返回只包含当前节点的列表。
3. 递归获取左子树中叶子节点到根节点的路径列表 left_paths。
4. 递归获取右子树中叶子节点到根节点的路径列表 right_paths。
5. 将当前节点加入到 left_paths 和 right_paths 中的每个路径的前面。
6. 返回 left_paths 和 right_paths 的合并列表,即为从叶子节点到根节点的路径列表。
下面是 Python 代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def leaf_to_root_paths(root: TreeNode) -> List[List[int]]:
if not root:
return []
if not root.left and not root.right:
return [[root.val]]
left_paths = leaf_to_root_paths(root.left)
right_paths = leaf_to_root_paths(root.right)
paths = []
for path in left_paths + right_paths:
paths.append([root.val] + path)
return paths
```
其中,TreeNode 是二叉树的节点类,leaf_to_root_paths 函数接收二叉树根节点,返回从叶子节点到根节点的路径列表。
阅读全文