以这个为头编一个非递归实现二叉树左右子树交换
时间: 2023-10-31 15:05:33 浏览: 49
以下是非递归实现二叉树左右子树交换的代码:
```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`,返回交换后的根节点。使用一个栈来存储还未交换左右子树的节点,首先将根节点压入栈中,然后进入循环:每次从栈顶取出一个节点,并交换其左右子树;如果该节点的左子树和右子树非空,则将它们按照左右顺序压入栈中。重复这个过程直到栈为空,最后返回交换后的根节点。
相关问题
非递归实现二叉树左右子树交换
二叉树左右子树交换可以使用非递归的方式实现,可以借助栈来完成。具体实现步骤如下:
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
def invertTree(root):
if not root:
return None
stack = [root]
while stack:
node = stack.pop()
if node:
node.left, node.right = node.right, node.left
stack.append(node.left)
stack.append(node.right)
return root
```
该函数使用了一个栈来实现非递归遍历二叉树,并在遍历的过程中交换了每个节点的左右子树。具体实现过程如下:
1. 首先将根节点入栈。
2. 当栈不为空时,弹出栈顶节点。
3. 如果该节点存在,则交换其左右子树,并将左右子树入栈。
4. 重复步骤2-3,直到栈为空。
5. 返回根节点。