剑指 Offer 27. 二叉树的镜像 - 力扣（LeetCode） (leetcode-cn.com)

剑指 Offer 28. 对称的二叉树 - 力扣（LeetCode） (leetcode-cn.com)

 

这两题都是有关二叉树的镜像问题。

我刚开始的思路是，使用BFS遍历二叉树，将每一层存到一个LinkedList中，按照层对二叉树进行镜像操作。

 1     public void test(TreeNode root) {
 2         if (root == null) {
 3             return true;
 4         }
 5         LinkedList<TreeNode> queue1 = new LinkedList<>(), queue2 = new LinkedList<>();
 6         queue1.offerLast(root);
 7         while (!queue1.isEmpty() || !queue2.isEmpty()) {
 8             if (!queue1.isEmpty()) {
 9                 //镜像操作
10                 function(queue1, queue2);
11             } else {
12                 //镜像操作
13                 function(queue2, queue1);
14             }
15         }
16     }
17 
18     public void function(LinkedList<TreeNode> queueOut, LinkedList<TreeNode> queueIn) {
19         TreeNode temp = null;
20         while (!queueOut.isEmpty()) {
21             temp = queueOut.pollFirst();
22             if (temp == null) {
23                 continue;
24             }
25             queueIn.offerLast(temp.left);
26             queueIn.offerLast(temp.right);
27         }
28     }

 

做Offer28的时候，这个方法的时间、空间开销感觉已经接近于无法通过了，于是开始思考递归的做法。

我刚开始使用的错误递归，是把二叉树的镜像问题想成了一个全局的递归问题，即：

• 二叉树本身是镜像的
• 二叉树的左右子树也都是镜像的

这就导致了在二叉树的镜像问题上，我的思路全部错误。

 

正确的镜像二叉树的定义是：

• 二叉树为空树
• 不为空树，则有：
  • left.left == right.right
  • left.right == right.left

 

由此，二叉树的镜像问题就转化为了非常标准的递归解法。

 1     public boolean isSymmetric(TreeNode root) {
 2         if (root == null) {
 3             return true;
 4         }
 5         return dfs(root.left, root.right);
 6     }
 7 
 8     public boolean dfs(TreeNode left, TreeNode right) {
 9         if (left == null && right == null) {
10             return true;
11         }
12         if (left == null && right != null) {
13             return false;
14         }
15         if (left != null && right == null) {
16             return false;
17         }
18         return left.val == right.val && dfs(left.left, right.right) && dfs(left.right, right.left);
19     }