递归实现二叉树左右子树交换
时间: 2023-06-14 19:02:41 浏览: 77
可以通过递归实现二叉树左右子树交换,具体实现如下所示:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 递归实现左右子树交换
def invertTree(root: TreeNode) -> TreeNode:
if not root:
return None
# 交换左右子树
root.left, root.right = root.right, root.left
# 递归处理左右子树
invertTree(root.left)
invertTree(root.right)
return root
```
在上述代码中,我们首先定义了一个二叉树节点类 `TreeNode`,其中包含了节点的值、左子树和右子树。接着,我们定义了一个 `invertTree` 函数,该函数通过递归实现了二叉树左右子树的交换。具体实现如下:
- 如果当前节点为空,则直接返回 `None`;
- 否则,我们先交换当前节点的左右子树;
- 然后,递归处理左子树和右子树;
- 最后,返回根节点。
通过以上递归处理,我们可以实现二叉树左右子树的交换。
相关问题
非递归实现二叉树左右子树交换
二叉树左右子树交换可以使用非递归的方式实现,可以借助栈来完成。具体实现步骤如下:
1. 声明一个栈,将根节点入栈。
2. 循环遍历栈,直至栈为空。循环中的操作如下:
a. 出栈一个节点,将其左右子节点交换。
b. 如果其左子节点不为空,则将左子节点入栈。
c. 如果其右子节点不为空,则将右子节点入栈。
以下是具体的实现过程的 Python 代码示例:
```python
def invert_tree(root):
if not root:
return None
stack = [root]
while stack:
node = stack.pop()
node.left, node.right = node.right, node.left
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return root
```
以上代码中,`root` 表示二叉树的根节点。函数 `invert_tree` 通过栈的方式遍历二叉树,并将每个节点的左右子树进行交换。最后返回根节点即可。
以这个为头编一个非递归实现二叉树左右子树交换
以下是非递归实现二叉树左右子树交换的代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invertTree(root: TreeNode) -> TreeNode:
if not root:
return None
stack = [root]
while stack:
node = stack.pop()
node.left, node.right = node.right, node.left
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return root
```
该函数的参数为根节点 `root`,返回交换后的根节点。使用一个栈来存储还未交换左右子树的节点,首先将根节点压入栈中,然后进入循环:每次从栈顶取出一个节点,并交换其左右子树;如果该节点的左子树和右子树非空,则将它们按照左右顺序压入栈中。重复这个过程直到栈为空,最后返回交换后的根节点。
相关推荐
![](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)