给定扩展二叉树的前序序列,构建二叉树,计算给定二叉树的所有左叶子之和。
时间: 2024-01-23 09:39:27 浏览: 39
首先,我们需要了解什么是扩展二叉树。扩展二叉树是一种二叉树的表示方法,其中每个非叶子节点都有两个子节点,但其中一个或两个子节点可以为空。因此,扩展二叉树的前序序列可以被表示为一个字符串,其中空节点用字符“#”表示。例如,扩展二叉树“1(2(4(#)(#))(5(#)(#)))”可以表示为前序序列“124##5##”。
现在我们来考虑如何构建二叉树。我们可以使用递归的方法来构建二叉树,每次递归都处理当前节点的左子树和右子树。具体来说,我们可以先读取前序序列中的下一个字符,如果当前字符是“#”,则表示该节点为空;否则,我们可以将该字符转换为数字并创建一个新节点,然后递归构建该节点的左子树和右子树。
下面是 Python 代码实现:
``` python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder):
def helper():
val = preorder.pop(0)
if val == '#':
return None
node = TreeNode(int(val))
node.left = helper()
node.right = helper()
return node
return helper()
```
接下来,我们需要计算给定二叉树的所有左叶子之和。左叶子是指没有右子树的左子树节点。因此,我们可以使用递归的方法遍历整个二叉树,在遍历的过程中累加所有左叶子节点的值。具体来说,对于每个节点,我们将其左子节点的值加入结果中,然后递归处理其左子树和右子树。
下面是 Python 代码实现:
``` python
def sumOfLeftLeaves(root):
def helper(node, is_left):
if not node:
return 0
if not node.left and not node.right and is_left:
return node.val
return helper(node.left, True) + helper(node.right, False)
return helper(root, False)
```
完整代码如下:
``` python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder):
def helper():
val = preorder.pop(0)
if val == '#':
return None
node = TreeNode(int(val))
node.left = helper()
node.right = helper()
return node
return helper()
def sumOfLeftLeaves(root):
def helper(node, is_left):
if not node:
return 0
if not node.left and not node.right and is_left:
return node.val
return helper(node.left, True) + helper(node.right, False)
return helper(root, False)
preorder = '1(2(4(#)(#))(5(#)(#)))'
root = buildTree(list(preorder))
print(sumOfLeftLeaves(root)) # 输出 4
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)