对称二叉树

男娘i 2022-12-08 15:52 202阅读 0赞

# 对称二叉树 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/symmetric-tree/

## 2、题目要求 ##

> 题目描述

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

> 示例

例如，二叉树 `[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

> **进阶：**

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

## 3、代码思路 ##

> 递归

递归解题思路

1.  额，怎么说呢？这道题其实感觉用迭代做起来可能更轻松一些，本着挑战的原则，我还是尝试了一下递归的解法，折腾了一会终于做出来了
2.  想想判断镜像的条件是什么呢？那肯定是位于镜像位的两个节点的值相等吧，所以题目给的 `boolean isSymmetric(TreeNode root) {` 函数不能作为递归函数，递归函数起码得要有两个形参，分别表示位于镜像位的两个节点，于是我们定义函数 `boolean isMirror(TreeNode leftNode, TreeNode rightNode) {` 用于递归判断 `leftNode` 为根节点的树与 `rightNode` 为根节点的树是否为镜像关系
3.  二话不说，递归先写回溯条件：递归至最深层，已经越过叶子节点时，开始回溯，即 `if (leftNode == null || rightNode == null) {` 开始回溯，那么回溯的返回值应该是什么呢？那得看 `leftNode` 和 `rightNode` 是否同时为空咯，如果同时为空则 `return true;`，表示 `leftNode` 与 `rightNode` 为镜像关系，否则 `return false;`，表示 `leftNode` 与 `rightNode` 不是镜像关系
4.  递归途中作相等判断：当 `leftNode.val == rightNode.val` 表示 `leftNode` 与 `rightNode` 为镜像关系，否则 `return false;`，表示 `leftNode` 与 `rightNode` 不是镜像关系，提前终止递归
5.  我们需要递归地判断 `leftNode` 与 `rightNode` 的子树是否为镜像关系，即获取 `isMirror(leftNode.left, rightNode.right)` 和 `isMirror(leftNode.right, rightNode.left)` 函数执行的返回值，如果是镜像关系，则 `return true`，表示为镜像关系，否则 `return false`，表示不是镜像关系

--------------------

举例说明

1.  二叉树如下
    
        1
           / \
          2   2
         / \ / \
        3  4 4  3
2.  首先执行 `isMirror(root.left, root.right);`，此时 `leftNode` 与 `rightNode` 的值均为 `2`
3.  因为 `leftNode.val == rightNode.val`，所以继续执行其子树的镜像判断，先判断 `leftNode` 的左子树是否与 `rightNode` 的右子树为镜像关系，即执行 `isMirror(leftNode.left, rightNode.right)`；然后判断 `leftNode` 的右子树是否与 `rightNode` 的左子树为镜像关系，即 `isMirror(leftNode.right, rightNode.left))`
4.  当递归执行到值为 `3` 的节点时，其左右子树均为空，执行两次 `return true` 开始回溯，此时 `isMirror(2.left, 2.right)` 函数执行结果为 `true`，由于是 `&&` 运算，此时还需要执行 `isMirror(2.right, 2.left)` 函数，同理，其执行结果为 `true`
5.  至此，整个递归执行完成，该二叉树为镜像二叉树，`return true;` 即可

> 迭代

迭代思路

1.  额，其实用迭代来做这道题，思路会更清晰，毕竟就是二叉树层序遍历的变种问题嘛
2.  我们维护一个队列来 `queue`，`queue` 中保存了二叉树当前层的节点，不过这可和二叉树的层序遍历不一样，我们对该 `queue` 中节点的存放顺序有严格要求，我们要求位于镜像位置的节点，必须在 `queue` 中连续存放
3.  这样我们判断当前层是否为镜像层时，就容易得多了，我们每次取出队列 `queue` 中连续的两个节点，判断这两个节点是否满足镜像节点的条件即可：要么同时为空，要么节点值相等
4.  问题来了：根节点只有一个，无法连续取出两个节点，这种特殊情况怎么处理？我们从第二层开始迭代，在初始化时，直接将 `root.left` 和 `root.right` 放入队列中
5.  当然，我们添加往 `queue` 中添加节点的顺序就要稍微改变一下啦，我们需要将处于镜像位置的节点放在 `queue` 中相邻的位置，即
    
        queue.offer(leftNode.left);
        queue.offer(rightNode.right);
        queue.offer(leftNode.right);
        queue.offer(rightNode.left);
6.  当执行完迭代之后，即 `queue.isEmpty() == true` 时，证明整棵二叉树为镜像二叉树，`return true;` 即可

## 4、代码实现 ##

递归

class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            // Guard Safe
            if (root == null) {
        
                return true;
            }
            // 递归判断 leftNode 为根节点的树与 rightNode 为根节点的树是否为镜像关系
            return isMirror(root.left, root.right);
        }
    
        /**
         * 递归判断 leftNode 为根节点的树与 rightNode 为根节点的树是否为镜像关系
         *
         * @param leftNode  位于二叉树左半部分的节点
         * @param rightNode 位于二叉树右半部分的节点
         * @return leftNode 与 rightNode 是否为镜像关系
         */
        public boolean isMirror(TreeNode leftNode, TreeNode rightNode) {
        
            // 递归至最深层，已经越过叶子节点时，开始回溯
            if (leftNode == null || rightNode == null) {
        
                if (leftNode == null && rightNode == null) {
        
                    // 如果同时为空则 return true;，表示 leftNode 与 rightNode 为镜像关系
                    return true;
                } else {
        
                    // 否则 return false;，表示 leftNode 与 rightNode 不是镜像关系
                    return false;
                }
            }
            // 递归途中作相等判断
            // 如果位于镜像位置的节点值相等，则递归进行判断
            // 如果树中每个节点都是镜像关系，则 return true;
            if (leftNode.val == rightNode.val
                    && isMirror(leftNode.left, rightNode.right)
                    && isMirror(leftNode.right, rightNode.left)) {
        
                return true;
            } else {
        
                // 否则， return false，表示不是镜像关系
                return false;
            }
        }
    }
    
    public class TreeNode {
        
        int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode(int x) {
        
            val = x;
        }
    }

迭代

class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            //Guard Safe
            if (root == null) {
        
                return true;
            }
            Deque<TreeNode> queue = new LinkedList<>();
            // 初始化时，将 root.left 和 root.right 放入队列中
            queue.offer(root.left);
            queue.offer(root.right);
            while (queue.isEmpty() == false) {
        
                int curLevelSize = queue.size();
                // 注意，由于每次取出两个节点，所以循环终止条件为 curLevelSize / 2
                for (int i = 0; i < curLevelSize / 2; i++) {
        
                    // 取出相邻的两个节点
                    TreeNode leftNode = queue.poll();
                    TreeNode rightNode = queue.poll();
                    // 满足镜像节点的条件：要么同时为空，要么节点值相等
                    if(leftNode==null && rightNode==null) {
        
                        continue;
                    }
                    if((leftNode==null || rightNode==null) || (leftNode.val != rightNode.val)){
        
                        return false;
                    }
                    // 将处于镜像位置的节点放在 queue 中相邻的位置
                    queue.offer(leftNode.left);
                    queue.offer(rightNode.right);
                    queue.offer(leftNode.right);
                    queue.offer(rightNode.left);
                }
            }
            return true;
        }
    }