求翻转二叉树的算法思路
时间: 2023-07-26 12:49:41 浏览: 52
翻转二叉树,可以采用递归的思路进行求解。具体思路如下:
1. 首先判断当前节点是否为空,如果为空则返回空。
2. 然后递归翻转当前节点的左子树和右子树。
3. 将当前节点的左子树赋值给右子树,将当前节点的右子树赋值给左子树。
4. 最后返回翻转后的当前节点。
代码实现如下:
```
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left = right
root.right = left
return root
```
这里需要注意的是,在交换左右子树的时候,可以采用一个中间变量来实现,也可以直接使用Python的多重赋值特性来实现。
相关问题
给我一段使用js写的反转二叉树算法
当然!以下是使用 JavaScript 编写的反转二叉树(翻转二叉树)的算法示例代码:
```javascript
function TreeNode(val, left, right) {
this.val = val;
this.left = left;
this.right = right;
}
function invertTree(root) {
if (root === null) {
return null;
}
var temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
// 示例用法:
var tree = new TreeNode(4);
tree.left = new TreeNode(2);
tree.right = new TreeNode(7);
tree.left.left = new TreeNode(1);
tree.left.right = new TreeNode(3);
tree.right.left = new TreeNode(6);
tree.right.right = new TreeNode(9);
console.log(invertTree(tree));
```
以上代码定义了一个名为 `TreeNode` 的构造函数,用于创建二叉树的节点。然后,定义了一个名为 `invertTree` 的函数,它接受一个二叉树的根节点作为参数,并返回反转后的二叉树的根节点。
在 `invertTree` 函数中,首先判断根节点是否为空,如果为空则直接返回 null。然后,通过交换根节点的左右子节点,实现对当前节点的翻转。接着,递归调用 `invertTree` 函数对当前节点的左子树和右子树进行翻转。最后,返回翻转后的根节点。
示例用法中创建了一个二叉树,并打印出反转后的二叉树的结构。你可以根据实际需求和二叉树的结构来使用这段代码。
设计一个python算法:给定一棵二叉树,要求输出其左右翻转后二叉树的中序遍历。 思路:镜像翻转:只需要遍历二叉树,每次访问一个结点时,交换其左右孩子,然后递归的翻转左右孩子。
好的,这是一个很有意思的问题,以下是我的 Python 实现:
```python
# 定义二叉树节点
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 镜像翻转二叉树
def mirror(root):
if not root:
return
root.left, root.right = root.right, root.left
mirror(root.left)
mirror(root.right)
# 中序遍历二叉树
def inorder(root):
if not root:
return []
res = []
res += inorder(root.left)
res.append(root.val)
res += inorder(root.right)
return res
# 获取左右翻转后的中序遍历结果
def get_flip_inorder(root):
# 镜像翻转二叉树
mirror(root)
# 获取左右翻转后的中序遍历结果
res = inorder(root)
# 再次镜像翻转二叉树,将其回复原状
mirror(root)
return res
# 测试代码
if __name__ == '__main__':
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
print(get_flip_inorder(root))
```
这个算法的时间复杂度是 $O(n)$,其中 $n$ 是二叉树中的节点数。