建立一棵以二叉链表形式储存的二叉树,以Bt指向根结点,P指向任一给定的结点,编程实现以字符形式输出从根节点到给定结点之间的路径
时间: 2023-12-29 07:05:13 浏览: 84
基于二叉链表的二叉树实现
5星 · 资源好评率100%
以下是Python代码实现:
```python
class TreeNode:
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
def buildTree(arr):
if not arr:
return None
root = TreeNode(arr[0])
queue = [root]
i = 1
while i < len(arr):
node = queue.pop(0)
if arr[i] is not None:
node.left = TreeNode(arr[i])
queue.append(node.left)
i += 1
if i < len(arr) and arr[i] is not None:
node.right = TreeNode(arr[i])
queue.append(node.right)
i += 1
return root
def findPath(root, target):
path = []
def dfs(node):
if not node:
return False
path.append(str(node.val))
if node.val == target.val:
return True
if dfs(node.left) or dfs(node.right):
return True
path.pop()
return False
dfs(root)
return path
if __name__ == '__main__':
arr = [1, 2, 3, None, 4, None, None, None, 5]
root = buildTree(arr)
target = root.right.left
path = findPath(root, target)
print('->'.join(path))
```
这里我们通过一个队列来构建二叉树,并且采用深度优先搜索来查找给定结点。当我们找到目标结点时,将路径上的结点值都添加到一个列表中,最后将其以字符串形式输出即可。
阅读全文