二叉树问题

对称二叉树

后记：此篇文章为自己在力扣刷题时所记，可能是当时觉得此题解法甚妙，也可能是看了答案觉得这么简单我本应能做出来。总之，此为刷题所记。

问题：给定一个二叉树，检查它是否是镜像对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

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

节点类代码：

  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }

解法一：深度遍历（递归）

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) {
            return true;
        }
        //调用递归函数，比较左节点，右节点
        return dfs(root.left,root.right);
    }

    boolean dfs(TreeNode left, TreeNode right) {
        //递归的终止条件是两个节点都为空
        //或者两个节点中有一个为空
        //或者两个节点的值不相等
        if(left==null && right==null) {
            return true;
        }
        if(left==null || right==null) {
            return false;
        }
        if(left.val!=right.val) {
            return false;
        }
        //再递归的比较 左节点的左子节点 和 右节点的右子节点
        //以及比较  左节点的右子节点 和 右节点的左子节点
        return dfs(left.left,right.right) && dfs(left.right,right.left);
    }
}

解法二：广度遍历（迭代）

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }

    public boolean check(TreeNode left,TreeNode right){
        //Linkedlist实现了Queue接口
        Queue<TreeNode> queue = new LinkedList<>();
        //offer方法是将元素添加到队列的末尾
        queue.offer(left);
        queue.offer(right);
        while(!queue.isEmpty()){
            //poll方法是将队列头部元素弹出
            left = queue.poll();
            right = queue.poll();

            if(left == null && right == null){
                continue;
            }
            if(left == null || right == null){
                return false;
            }
            if(left.val != right.val){
                return false;
            }

            queue.offer(left.left);
            queue.offer(right.right);

            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }
}