用递归算法删除带头结点的单链表中值为x的元素
时间: 2024-06-14 12:03:43 浏览: 17
以下是用递归算法删除带头结点的单链表中值为x的元素的Python实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeElements(head: ListNode, val: int) -> ListNode:
if not head:
return None
head.next = removeElements(head.next, val)
return head.next if head.val == val else head
```
相关问题
查找二叉树中值为x的结点的算法
查找二叉树中值为x的结点的算法可以通过递归实现,具体步骤如下:
1. 如果根结点为空,返回空;
2. 如果根结点的值等于x,返回该结点;
3. 如果x小于根结点的值,则在左子树中查找;
4. 如果x大于根结点的值,则在右子树中查找;
5. 如果在子树中找到了值为x的结点,则返回该结点;
6. 如果在子树中没有找到值为x的结点,则返回空。
下面是一个示例代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def searchNode(root, x):
if not root:
return None
if root.val == x:
return root
elif x < root.val:
return searchNode(root.left, x)
else:
return searchNode(root.right, x)
```
其中,TreeNode是二叉树的节点类。```searchNode```函数接收一个根节点和需要查找的值x,返回值为找到的节点或者空。
删除二叉树的子树:假设二叉树中的结点均不相等,采用二叉链存储,设计递归算法删除根结点值为x的子树。
可以回答这个问题。递归删除根结点值为x的子树的算法如下:
1. 如果当前结点为空,则返回空。
2. 如果当前结点的值等于x,则将左右子树都置为空,返回空。
3. 递归删除左子树中值为x的子树。
4. 递归删除右子树中值为x的子树。
5. 如果当前结点的左子树不为空且值等于x,则将左子树置为空。
6. 如果当前结点的右子树不为空且值等于x,则将右子树置为空。
7. 返回当前结点。
代码实现如下:
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
TreeNode* deleteSubtree(TreeNode* root, int x) {
if (root == nullptr) {
return nullptr;
}
if (root->val == x) {
root->left = nullptr;
root->right = nullptr;
return nullptr;
}
root->left = deleteSubtree(root->left, x);
root->right = deleteSubtree(root->right, x);
if (root->left != nullptr && root->left->val == x) {
root->left = nullptr;
}
if (root->right != nullptr && root->right->val == x) {
root->right = nullptr;
}
return root;
}