描述

题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

示例

输入：{8,6,6,5,7,7,5}
返回值：true

知识点：二叉树
难度：⭐⭐⭐⭐

题解

解题思路

因为要比较左右结点是否对称，因此可以通过BFS每次对一层的结点进行遍历并比较是否对称。

对于树的问题，往往还可以通过递归解决，相对于遍历，代码量会少很多，但没有遍历容易理解。

方法一：BFS 广度优先遍历

图解

算法流程：

• 1、每次往队列中按顺序，从左到右放入当前结点的左右子节点，随后进行判断。

  2、每次从Queue中获取前两个元素，并比较值

  3、如果又一对元素比较结果不相等，则表示不对称。

  4、注意放入队列的顺序，左子结点的左子结点、右子结点的右子结点、左结点的右子结点、右结点的左子结点放入队列。

Java 版本代码如下：

import java.util.*;
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot == null) {
            return true;
        }
        return bfs(pRoot);
    }

    boolean bfs(TreeNode root) {
        if(root == null) {
            return true;
        }
        // BFS通常借助队列实现
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);

        while(!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            // 表示bfs已经进行到叶子结点了，
            if(left == null && right == null) {
                continue;                
            }
            // 判断是否对称
            if(left == null || right == null || left.val != right.val) {
                return false;                
            }
            // 对下一层的每个结点，都放入队列中
            // 注意放入队列的顺序，左子结点的左子结点、右子结点的右子结点、左结点的右子结点、右结点的左子结点放入队列。
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(right.left);
            queue.offer(left.right);
        }
        return true;        
    }
}

复杂度分析：

时间复杂度 O(N)：对每一层的左右对称两个结点都要进行比较
空间复杂度 O(N)：需要借助队列实现BFS

方法二：递归

对于递归方法，最重要的是能清晰地定义递归函数的功能并实现，而且只需要在调用递归函数的时候直接使用该功能即可，不能跳入递归逻辑当中，只需要认准 ”调用即实现“ 即可。

算法流程：

• 构建递归函数：
  • 定义函数功能：判断左右两个结点是否对称相等
  • 递归终止条件:
    • 没有子节点，说明当前结点是叶子结点
    • 没有右子节点（因为是按从左到右的顺序比较的）
    • 左右结点不对称

Java 版本代码如下：

public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        if(pRoot == null){
            return true;
        }
        // 递归调用
        return recur(pRoot.left, pRoot.right);
    }

    // 递归函数功能：判断左右两个结点是否对称相等
    private boolean recur(TreeNode left, TreeNode right) {
        // 没有子节点，说明当前结点是叶子结点
        if(left == null) {
            return right == null;
        }
        // 没有右子节点
        if(right == null) {
            return false;
        }
        // 左右结点不对称
        if(left.val != right.val) {
            return false;
        } 
        // 左子树的右子树和右子树的左子树相同即可
        return recur(left.right, right.left) && recur(left.left, right.right);
    }
}

复杂度分析：

时间复杂度 O(N)：递归次数平均为节点数
空间复杂度 O(N)：最坏情况下，二叉树退化为链表