递归算法求解二叉树中度为2的节点数
时间: 2024-08-14 09:04:34 浏览: 37
递归算法可以有效地解决二叉树中度为2的节点(也称为度为2的分支或结点)的问题。在这个问题上,我们通常会考虑以下步骤:
1. **基本情况**:如果给定的二叉树为空,那么它自然没有度为2的节点,返回0。
2. **递归情况**:对于非空的二叉树,我们需要分别检查左子树和右子树:
- 计算左子树中度为2的节点数。
- 计算右子树中度为2的节点数。
- **关键操作**:增加当前节点自身度为2的情况,即当前节点有两个子节点。这发生在当且仅当`left_child`(左孩子)存在并且`right_child`(右孩子)也存在时。
- 将左右子树的结果相加,加上当前节点的特殊情况。
递归公式可以表示为:
```python
def count_degree_two(root):
if root is None:
return 0
left_count = count_degree_two(root.left)
right_count = count_degree_two(root.right)
# 如果当前节点有两个子节点,则计数加1
degree_two_nodes = (left_count + right_count) + int(root.left and root.right)
return degree_two_nodes
```
其中,`root`是对二叉树根节点的引用。
相关问题
递归算法 求二叉树的高度
要求二叉树的高度,可以使用递归算法来实现。下面是一个示例的递归算法,用于计算二叉树的高度:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def get_tree_height(root):
if root is None: # 如果根节点为空,说明是空树,高度为0
return 0
else:
left_height = get_tree_height(root.left) # 递归计算左子树的高度
right_height = get_tree_height(root.right) # 递归计算右子树的高度
return max(left_height, right_height) + 1 # 返回左右子树中较大的高度加1
```
在这个递归函数中,我们首先判断根节点是否为空,如果为空,则返回0,因为空树高度为0。否则,我们递归计算左子树和右子树的高度,然后取左右子树中较大的高度,并加1,即为整个二叉树的高度。
使用这个递归函数,可以方便地求解任意二叉树的高度。
非递归算法求二叉树的叶结点个数C++
可以使用迭代法(非递归算法)来求解二叉树的叶结点个数,具体思路如下:
1.定义一个计数器 count,初始化为0。
2.使用栈来遍历二叉树。首先将根节点入栈。
3.进入循环,当栈不为空时执行以下操作:
- 弹出栈顶元素,如果该元素为叶结点,则将 count 加1。
- 如果该元素有右子树,则将右子树入栈。
- 如果该元素有左子树,则将左子树入栈。
4.遍历结束后,返回 count 值即可。
下面是C++代码实现:
```c++
int countLeaves(TreeNode* root) {
if (!root) {
return 0;
}
int count = 0;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
if (!node->left && !node->right) {
count++;
}
if (node->right) {
st.push(node->right);
}
if (node->left) {
st.push(node->left);
}
}
return count;
}
```
其中,TreeNode 表示二叉树的节点。