给你一个二叉树的根节点 root ，检查它是否轴对称。
示例1：
输入：root = [1,2,2,3,4,4,3]
输出：true

  1.       1      
  2.     /   \    
  3.   2       2  
  4.  / \     / \ 
  5. 3   4   4   3

示例2：
输入：root = [1,2,2,null,3,null,3]
输出：false

  1.       1      
  2.     /   \    
  3.   2       2  
  4.    \       \ 
  5.     3       3

分析

对于根节点来说，左子树和右子树每个节点都一致，则表示二叉树轴对称。
那么需要有个方法可以对比左子树的每一个节点和右子树的每一个节点

  1. private boolean check(TreeNode left, TreeNode right) {
  3. }

两个节点自身比较是比较简单的，只要比较节点的值是否相等

  1. left.val == right.val

但是如何递归比较呢？

参考示例1的二叉树：

  1.       1      
  2.     /   \    
  3.   2       2  
  4.  / \     / \ 
  5. 3   4   4   3

根节点的左子树的左子节点 3 需要和 根节点的右子树的右子节点 3 比较
根节点的左子树的右子节点 4 需要和 根节点的右子树的左子节点 4 比较
即应该递归比较 left 节点的左子节点和 right 节点的右子节点并且同时比较 left 节点的右子节点和 right 节点的左子节点

  1. left.val == right.val && check(left.left, right.right) && check(left.right, right.left)

边界情况分析

  • 如果 left 和 right 都为空，那么可以认为递归比较结束了，无需继续递归调用，且之前的节点都是相同的，二叉树是轴对称的
  • 如果 left 或 right 有一个为空，那么二叉树肯定就不轴对称了
    1. if(left == null && right == null) {
    2.   return true;
    3. }
    4. if(left == null || right == null) {
    5.   return false;
    6. }
    完整的 check 方法：
    1. private boolean check(TreeNode left, TreeNode right) {
    2.   if(left == null && right == null) {
    3.       return true;
    4.   }
    5.   if(left == null || right == null) {
    6.       return false;
    7.   }
    8.   return left.val == right.val && check(left.left, right.right) && check(left.right, right.left);
    9. }
    但是 isSymmetric 方法如何调用 check 方法呢？

我们可以把示例1 理解为如下的两棵树：

  1.     1    1      
  2.    /      \    
  3.   2        2  
  4.  / \      / \ 
  5. 3   4    4   3

那么 isSymmetric 方法调用可以按如下方式调用 check 方法：

  1. check(root, root);

完整递归算法

  1. public boolean isSymmetric(TreeNode root) {
  2.     return check(root, root);
  3. }
  5. private boolean check(TreeNode left, TreeNode right) {
  6.     if(left == null && right == null) {
  7.         return true;
  8.     }
  9.     if(left == null || right == null) {
  10.         return false;
  11.     }
  12.     return left.val == right.val && check(left.left, right.right) && check(left.right, right.left);
  13. }

递归如何转迭代？

递归都是可以转迭代的，递归转迭代需要借用其他的数据结构暂存一下需要比较的元素（比如队列或者栈），并且需要一直循环比较，直至所有的元素都完成比较：

  1. private boolean check(TreeNode left, TreeNode right) {
  2.     Queue<TreeNode> queue = new LinkedList<TreeNode>();
  4.     while(!queue.isEmpty()) {
  6.     }
  7. }

那在 while 循环前需要做什么？在 while 循环里面又需要做什么？什么时候跳出结束 while 循环？

  • while 循环前需要提前往队列里面放入需要比较的元素；

  • while 循环里面就是比较两个节点是否一致以及是否需要结束循环

    • 从队列中取出需要比较的元素，并比较元素是否一致
    • 比较时如果检查发现树已经不满足轴对称了，则可以提前跳出结束 while 循环了
      1. private boolean check(TreeNode left, TreeNode right) {
      2. Queue<TreeNode> queue = new LinkedList<TreeNode>();
      3. queue.offer(left);
      4. queue.offer(right);
      5. while(!queue.isEmpty()) {
      6.    right = queue.poll();
      7.    left = queue.poll();
      8.    if(left == null && right == null) {
      9.        continue;
      10.    }
      11.    if((left == null || right == null) || (left.val != right.val)) {
      12.        return false;
      13.    }
      14. }
      15. }
      一次循环结束，在下次循环开始之前，还需要重新往队列中放入需要比较的元素：
      参考递归中的分析：比较 left 节点的左子节点和 right 节点的右子节点并且同时比较 left 节点的右子节点和 right 节点的左子节点
      所以往队列中放入元素的顺序有要求：

  • 放入 left 节点的左子节点后需要放入 right 节点的右子节点

  • 放入 left 节点的右子节点后需要放入 right 节点的左子节点

    1. private boolean check(TreeNode left, TreeNode right) {
    2.   Queue<TreeNode> queue = new LinkedList<TreeNode>();
    3.   queue.offer(left);
    4.   queue.offer(right);
    5.   while(!queue.isEmpty()) {
    6.       right = queue.poll();
    7.       left = queue.poll();
    8.       if(left == null && right == null) {
    9.           continue;
    10.       }
    11.       if((left == null || right == null) || (left.val != right.val)) {
    12.           return false;
    13.       }
    15.       queue.offer(left.left);
    16.       queue.offer(right.right);
    18.       queue.offer(left.right);
    19.       queue.offer(right.left);
    20.   }
    21. }

    完整迭代算法

    ```java public boolean isSymmetric(TreeNode root) { return check(root, root); }

private boolean check(TreeNode left, TreeNode right) { Queue queue = new LinkedList(); queue.offer(left); queue.offer(right); while(!queue.isEmpty()) { right = queue.poll(); left = queue.poll(); if(left == null && right == null) { continue; } if((left == null || right == null) || (left.val != right.val)) { return false; }

  1.     queue.offer(left.left);
  2.     queue.offer(right.right);
  4.     queue.offer(left.right);
  5.     queue.offer(right.left);
  6. }
  7. return true;

} ```