剑指 Offer 27. 二叉树的镜像【递归、迭代】
题目描述
请完成一个函数,输入一个二叉树,该函数输出它的镜像。
例如输入:
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出:
4
/ \
7 2
/ \ / \
9 6 3 1
示例 1:
1 | 输入:root = [4,2,7,1,3,6,9] |
解题思路
方法一:递归
代码实现
1 | public TreeNode mirrorTree(TreeNode root) { |
复杂度分析
时间复杂度:O(n)
空间复杂度:O(n)
方法二:迭代
将未交换的结点存入栈中,将交换的结点的孩子节点存入栈,使得每个结点都交换左右孩子结点即可。
代码实现
1 | public TreeNode mirrorTree2(TreeNode root) { |
复杂度分析
时间复杂度:O(n)
空间复杂度:O(n)
资源
剑指 Offer 27. 二叉树的镜像【递归、迭代】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.