二叉树镜像
题目描述
操作给定的二叉树,将其变换为源二叉树的镜像。
分析:
想到递归,对每一个节点有4种情况:
-
当前节点为空
-
当前节点不为空,左子树为空
-
当前节点不为空,右子树为空
-
当前节点不为空,左右子树都为空
很显然2,3
两点可以重合
那么递归退出条件就是1
和4
代码
代码如下,测试通过
public static void mirror(TreeNode root) {
if (root==null)return;
if (root.left==null && root.right==null) return;
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
mirror(root.left);
mirror(root.right);
}
总结
二叉树的递归,遵循以下几步:
-
找出所有情况
-
确定退出条件
-
确定一般递归内容
这一题题目现在看来不难,但是我一开始想偏了,想利用一个辅助函数helper(TreeNode left, TreeNode right)
来递归他的左子树和右子树,但是问题在于,每次交换左右子树都变化了,结果就是对于满二叉树可以完成,但是对于不是满二叉树就不行
阅读次数: 本文累计被阅读 1000000 次