请完成一个函数,输入一个二叉树,该函数输出它的镜像。
解题思路:
要求一棵树的镜像,其实就是将树的的左右子节点交换一下,类似于交换数组中两个位置的元素。
递归函数
终止条件:当 $root$ 为 $null$ 时,返回 $null$;
递推工作:
- 使用 $tmp$ 变量保存 $root.left$。
- 把 $root$.left 指向 右节点 的递归结果 $mirrorTree(root.right)$。
- 把 $root.right$ 指向原先保存的 左子树 的递归结果 $mirrorTree(tmp)$。
- 返回 root。
代码:
public TreeNode mirrorTree(TreeNode root) {
if(root == null) {
return null;
}
TreeNode tmp = root.left;
root.left = mirrorTree(root.right);
root.right = mirrorTree(tmp);
return root;
}
复杂度分析
-
时间复杂度$O(N)$ :其中 $N$ 为树的节点数量,交换工作需要遍历所有节点。
-
空间复杂度$O(N)$:最差情况下,树退化成链表,递归栈的占用 $O(N)$ 大小。
评论区