对称二叉数[简单]

红太狼 2024-02-19 11:03 6阅读 0赞

优质博文：[IT-BLOG-CN][]

### 一、题目 ###

给你一个二叉树的根节点`root`， 检查它是否轴对称。

**示例 1：**

![e10f3cfb9764439e84bcd509fe07bb21.png][]

输入：`root = [1,2,2,3,4,4,3]`  
输出：`true`

**示例 2：**

![e3496eb8ad964a0b82846415f804e142.png][]

输入：`root = [1,2,2,null,3,null,3]`  
输出：`false`

> 树中节点数目在范围`[1, 1000]`内  
> `-100 <= Node.val <= 100`

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

### 二、代码 ###

**【1】递归：** 我们将一个树的左右节点相同，转换为两个根节点具有相同的值，每个树的右子树都与另一个树的左子树镜像对称。我们通过一个递归函数，通过同步移动两个指针的方式来遍历树，`rootLeft`和`rootRight`都指向一个树的根，然后`rootLeft`右移时，`rootRight`左移，`rootLeft`左移时，`rootRight`右移。检查`rootLeft`和`rootRight`的值是否相等，如果相等再判断左右子树是否对称。

/**
     * Definition for a binary tree node.
     * 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) {
        
            return check(root, root);
        }
        private boolean check(TreeNode rootLeft, TreeNode rootRight) {
        
            if (rootLeft == null && rootRight == null) {
        
                return true;
            }
            if (rootLeft == null || rootRight == null) {
        
                return false;
            }
            return rootLeft.val == rootRight.val && check(rootLeft.left, rootRight.right) && check(rootLeft.right, rootRight.left);
        }
    }
    **时间复杂度：** 这里遍历了这棵树，渐进时间复杂度为`O(n)`。  
    **空间复杂度：** 这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过`n`，故渐进空间复杂度为`O(n)`。

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

/**
     * Definition for a binary tree node.
     * 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) {
        
            return check(root, root);
        }
        private boolean check(TreeNode rootLeft, TreeNode rootRight) {
        
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.offer(rootLeft);
            q.offer(rootRight);
            while(!q.isEmpty()) {
        
                rootLeft = q.poll();
                rootRight = q.poll();
                if (rootLeft == null && rootRight == null) {
        
                    continue;
                }
                if ((rootLeft == null || rootRight == null) || (rootLeft.val != rootRight.val)) {
        
                    return false;
                }
                q.offer(rootLeft.left);
                q.offer(rootRight.right);
    
                q.offer(rootLeft.right);
                q.offer(rootRight.left);
            }
            return true;
        }
    }

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

[IT-BLOG-CN]: https://it-blog-cn.com/blogs/algorithm/topic/easy/overreturn_tree.html
[e10f3cfb9764439e84bcd509fe07bb21.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/0ff07d9048d74c08b07157bd4d6aacff.png
[e3496eb8ad964a0b82846415f804e142.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/a3c3abc1088f4d17806fdde6c0cb265e.png