对称二叉树两种判定方法

偏执的太偏执、 2022-12-28 12:47 187阅读 0赞

### 题目描述： ###

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

//二叉树镜像对称
        1
       / \
      2   2
     / \ / \
    3  4 4  3
    //不是镜像对称
        1
       / \
      2   2
       \   \
       3    3

### 方法一：递归 ###

### 算法思路： ###

如果一个树的左子树与右子树镜像对称，那么这个树是对称的。因此该问题可以转化为：两个树在什么情况下互为镜像。

如果同时满足下面两个条件，两个树互为镜像：

*  它们的两个根节点具有相同的值
 *  每个树的右子树都与另一个树的左子树镜像对称

我们可以实现这样一个递归函数，通过同步移动两个指针的方法来遍历这棵树，p指针和q指针一开始都指向这棵树的根，随后p右移时，q左移，p左移时，q右移。每次检查当前p和q结点的值是否相等，如果相等在判断左右子树是否对称。

### 算法java实现： ###

public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }
    
    public boolean check(TreedNode p, TreedNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }

### 复杂度分析： ###

**假设树上一共有n个结点：**

*  时间复杂度：这里遍历了树，渐进复杂度为O(n)
 *  空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过n，故渐进空间复杂度为O(n)

### 方法二：迭代 ###

### 算法思路： ###

首先，我们引入一个[队列][Link 1]，这是把递归程序改写成迭代程序的常用方法。初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续点）时，该算法结束。

### 算法java实现： ###

//对称二叉树：迭代方法
        public static boolean isSymmetricTwo(TreeNode root) {
            return check(root,root);
        }
    
        public static boolean checkTwo(TreeNode u, TreeNode v) {
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.offer(u);
            q.offer(v);
            while (!q.isEmpty()) {
                u = q.poll();
                v = q.poll();
                if (u == null && v == null) {
                    continue;
                }
                if ((u == null || v == null) || (u.val != v.val)) {
                    return false;
                }
    
                q.offer(u.left);
                q.offer(v.right);
    
                q.offer(u.right);
                q.offer(v.left);
            }
            return true;
        }

### 复杂度分析： ###

*  时间复杂度：O(n)
 *  空间复杂度：这里需要用一个队列来维护结点，每个结点最多进队一次，出队一次，队列中最多不会超过n个点，故渐进空间复杂度为O(n)

**相关博文：[java queue详解 ][Link 1]**

[Link 1]: https://blog.csdn.net/li_w_ch/article/details/111309958