输出二叉树中所有度为1的结点
时间: 2023-05-25 15:05:37 浏览: 108
对于一个二叉树,其度为1的结点指的是只有一个子节点的结点。
我们可以使用递归的方式来遍历二叉树,检查每个结点是否为度为1的结点,如果是就加入结果数组中。具体实现如下:
```
# 定义二叉树结点
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 寻找二叉树中所有度为1的结点
def findDegreeOneNodes(root):
# 如果结点为空,直接返回空数组
if not root:
return []
# 如果结点左右子树都为空,说明该结点是叶子节点,没有子节点
if not root.left and not root.right:
return []
# 如果结点左右子树有一个为空,说明该结点是度为1的结点
if not root.left or not root.right:
return [root.val] + findDegreeOneNodes(root.left) + findDegreeOneNodes(root.right)
# 如果结点左右子树都不为空,继续递归遍历左右子树
return findDegreeOneNodes(root.left) + findDegreeOneNodes(root.right)
```
上述代码中,我们首先分别考虑了三种情况:
- 如果当前结点为空,说明此时遍历到叶子节点了,直接返回空数组。
- 如果当前结点既没有左子树也没有右子树,说明该结点是叶子节点,也没有任何度数,返回空数组。
- 如果当前结点只有左子树或者只有右子树,说明该结点是度数为1的结点,返回该结点的值以及左右子树的递归结果。
最后,当当前结点既有左子树也有右子树时,将其左右子树的递归结果合并起来作为本次递归的结果。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)