二叉树-对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
 

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

你可以运用递归和迭代两种方法解决这个问题吗？

1.递归方法

判断对称的条件，就是（如下图1），左子树L = 右子树R，再细分就是:

I. 左子树的左孩子等于右子树的右孩子：L.left = R.right
II. 左子树的右孩子等于右子树的左孩子：L.right = R.left

根据上面的判断条件由根节点往下递归：

· 当root根节点为空的时候直接返回true
· 当L和R两个节点都为空的时候，说明已经同时超过叶节点了，返回true
· 当L或者R只有一个节点超过叶节点了，说明树是不对称的返回false
· 当L 值 ≠ R 值，说明树是不对称的返回false

复杂度分析：

时间复杂度 O(N）：其中 N 为二叉树的节点数量，每次执行递归可以判断一对节点是否对称，因此最多只需递归 N/2 次。
空间复杂度 O(N) ：最差情况下，二叉树退化为链表，系统使用 O(N)大小的栈空间。

二叉树退化为链表
          1
         / \
        2   2
       /     \
      3       3
     /         \
    4           4

1.png

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
     public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return recur(root.left,root.right);
     }

     boolean recur(TreeNode L,TreeNode R){
        //如果两个节点都为空直接continue下一个循环，如果两个节点不相等就返回false，如果其中一个节点为空就返回false
        if(L == null && R == null) return true;
        if(L == null || R == null) return false;
        if(L.val != R.val) return false;
        return recur(L.left,R.right) && recur(L.right, R.left);
    }
}

2.迭代方法

判断条件和上面的递归是一样的，用层序遍历（ BFS），一层一层的遍历，将用来做对比的一对对树节点存入队列，然后再一对一对节点拿出来比较

复杂度分析：

时间复杂度 O(N）：其中 N 为二叉树的节点数量，每次执行迭代可以判断一对节点是否对称，因此最多只需递归 N/2 次。
空间复杂度 O(N) ：采用了额外空间，队列里面存储了树的节点。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        //使用层序遍历，将每一层节点放入
        Queue<TreeNode> queue = new LinkedList<>();
        //将左子树节点和右子树节点按顺序放进去队列
        queue.add(root.left);
        queue.add(root.right);
        while(!queue.isEmpty()){
            TreeNode L = queue.poll();
            TreeNode R = queue.poll();
            //如果两个节点都为空直接continue下一个循环，如果两个节点不相等就返回false，如果其中一个节点为空就返回false
            if(L == null && R == null) continue;
            if(L == null || R == null) return false;
            if(L.val != R.val) return false;

            //将左子树的左孩子和右子树的右孩子放进队列，待下一个循环拿出来对比是否相等
            queue.add(L.left);         
            queue.add(R.right);
            
            //将左子树的右孩子和右子树的左孩子放进队列，待下一个循环拿出来对比是否相等
            queue.add(L.right);         
            queue.add(R.left);
        }
        return true;
    }
}