14_对称二叉树

简介: 14_对称二叉树

对称二叉树

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

示例 1:

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

示例 2:

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

【思路】

对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一点就知道了其实我们要比较的是两个树(这两个树是根节点的左右子树),所以在递归遍历的过程中,也是要同时遍历两棵树。比较的是两个子树的里侧和外侧的元素是否相等。

那么遍历的顺序应该是什么样的呢?

本题遍历只能是“后序遍历”,因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。

正是因为要遍历两棵树而且要比较内侧和外侧节点,所以准确的来说是一个树的遍历顺序是左右中,一个树的遍历顺序是右左中。

但都可以理解算是后序遍历,尽管已经不是严格上在一个树上进行遍历的后序遍历了。

其实后序也可以理解为是一种回溯。

递归法

递归三部曲

1、确定递归函数的参数和返回值

因为我们要比较的是根节点的两个子树是否是相互翻转的,进而判断这个树是不是对称树,所以要比较的是两个树,参数自然也是左子树节点和右子树节点。

返回值自然是bool类型。

2、确定终止条件

要比较两个节点数值相不相同,首先要把两个节点为空的情况弄清楚!否则后面比较数值的时候就会操作空指针了。

节点为空的情况有:(注意我们比较的其实不是左孩子和右孩子,所以如下我称之为左节点右节点)

  • 左节点为空,右节点不为空,不对称,return false
  • 左不为空,右为空,不对称 return false
  • 左右都为空,对称,返回true

此时已经排除掉了节点为空的情况,那么剩下的就是左右节点不为空:

  • 左右都不为空,比较节点数值,不相同就return false

此时左右节点不为空,且数值也不相同的情况我们也处理了。

if (left == null && right != null)  return false;
else if (left != null && right == null) return false;
else if (left == null && right == null)  return true;
else if (left.val != right.val)  return false;//这里我没有使用else

注意上面最后一种情况,我没有使用else,而是else if, 因为我们把以上情况都排除之后,剩下的就是 左右节点都不为空,且数值相同的情况。

3、确定单层递归的逻辑

此时才进入单层递归的逻辑,单层递归的逻辑就是处理左右节点都不为空,且数值相同的情况。

  • 比较二叉树外侧是否对称:传入的是左节点的左孩子,右节点的右孩子
  • 比较内侧是否对称,传入左节点的右孩子,右节点的左孩子
  • 如果左右都对称就返回true,有一侧不对称就返回false
bool outside = compare(left.left, right.right);
bool inside = compare(left.right, right.left);
bool isSame = outside && inside;
return isSame;

完整代码如下所示:

import java.util.LinkedList;
/**
 * 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) {
        if (root == null) return true;
        return compare(root.left, root.right);
    }
    public boolean compare(TreeNode left, TreeNode right) {
        //确定递归终止条件
        if (left == null && right != null) {
            return false;
        } else if (left != null && right == null) {
            return false;
        } else if (left == null && right == null) {
            return true;
        // 排除了空节点,再排除值不相同的情况
        } else if (left.val != right.val) {
            return false;
        }
        // 此时就是:左右节点都不为空,且数值相同的情况
        // 此时才做递归,做下一层的判断
        boolean inSide = compare(left.right, right.left);
        boolean outside = compare(left.left, right.right);
        return inSide && outside;
    }
}

方法二:迭代法

使用队列

通过队列来判断根节点的左子树和右子树的内侧和外侧是否相等。

/
**  迭代法
**  使用双端队列,相当于两个栈
/
public boolean isSymmetric(TreeNode root) {
  Deque<TreeNode> deque = new LinkedList<>();
    deque.offerFirst(root.left);
    deque.offerLast(root.right);
    while (!deque.isEmpty()) {
        TreeNode leftNode = deque.pollFirst();
        TreeNode rightNode = deque.pollLast();
        if (leftNode == null && rightNode == null) {
            continue;
        }
        // 以上三个判断条件合并
        if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
            return false;
        }
        deque.offerFirst(leftNode.left);
        deque.offerFirst(leftNode.right);
        deque.offerLast(rightNode.right);
        deque.offerLast(rightNode.left); 
    }
    return true;
}

方法三:迭代法

使用普通队列

public boolean isSymmetric(TreeNode root) {
    Queue<TreeNode> deque = new LinkedList<>();
    deque.offer(root.left);
    deque.offer(root.right);
    while (!queue.isEmpty()) {
      TreeNode leftNode = deque.poll();
            TreeNode rightNode = deque.poll();
            if (leftNode == null && rightNode == null) {
                continue;
            }
            //以上三个条件合并
            if (leftNode == null || rightNode == null || leftNode.val != right.val)
                return false;
            //这里顺序与使用Deque不同
            deque.offer(leftNode.left);
            deque.offer(rightNode.right);
            deque.offer(leftNode.right);
            deque.offer(rightNode.left);
    }
    return true;
}


相关文章
|
5月前
|
人工智能 自然语言处理 搜索推荐
阿里云开发者实践:黄小宇GEO实验第14天——大模型复测与实体识别优化
这是黄小宇个人GEO实验第14天记录,聚焦阿里云技术栈下的数据处理与脚本优化,验证结构化内容能否提升大模型对“黄小宇”实体的稳定识别、降低同名混淆,并增强AI个人名片可见度。(239字)
|
5月前
|
机器学习/深度学习 人工智能 供应链
数据建模怎么做?一文解析8种经典数据建模方法
本文系统梳理8种经典数据建模方法(回归、分类、聚类、主成分分析、因子分析、关联规则、时间序列及探索式聚类),聚焦业务场景、适用条件与落地要点,破除“建模=高门槛”的误解,强调模型需扎根数据治理基础,真正服务于分析、决策与运营。
|
搜索推荐 Linux 调度
Util Linux 命令列表
Util Linux 是 Linux 系统核心工具集,提供近百个底层系统管理命令,涵盖磁盘分区(addpart/delpart)、文件系统操作(mkfs/fsck/fstrim)、设备信息查询(lsblk/lscpu/blkid)、进程控制(chrt/ionice/prlimit)、命名空间管理(nsenter/unshare)及硬件交互(rtcwake/wdctl)等,是系统维护与调试的必备套件。
|
10月前
|
运维 Cloud Native 应用服务中间件
阿里云微服务引擎 MSE 及 API 网关 2025 年 12 月产品动态
阿里云微服务引擎 MSE 面向业界主流开源微服务项目, 提供注册配置中心和分布式协调(原生支持 Nacos/ZooKeeper/Eureka )、云原生网关(原生支持Higress/Nginx/Envoy,遵循Ingress标准)、微服务治理(原生支持 Spring Cloud/Dubbo/Sentinel,遵循 OpenSergo 服务治理规范)能力。API 网关 (API Gateway),提供 APl 托管服务,覆盖设计、开发、测试、发布、售卖、运维监测、安全管控、下线等 API 生命周期阶段。帮助您快速构建以 API 为核心的系统架构.满足新技术引入、系统集成、业务中台等诸多场景需要。
|
Java 数据库连接 开发者
Spring Framework 核心技术详解
本文档旨在深入解析 Java Spring Framework 的核心技术原理与应用。与侧重于快速开发的 Spring Boot 不同,本文将聚焦于 Spring 框架本身的设计理念、核心容器、控制反转(IoC)、面向切面编程(AOP)、数据访问与事务管理等基础且强大的模块。通过理解这些核心概念,开发者能够更深刻地领悟 Spring 生态系统的设计哲学,并具备解决复杂企业级应用开发问题的能力。
750 4
|
JSON Java API
jackson序列化和反序列化中的注解和扩展点大全【收藏】
jackson序列化和反序列化中的注解和扩展点大全【收藏】
|
网络协议 Java Shell
java spring 项目若依框架启动失败,启动不了服务提示端口8080占用escription: Web server failed to start. Port 8080 was already in use. Action: Identify and stop the process that’s listening on port 8080 or configure this application to listen on another port-优雅草卓伊凡解决方案
java spring 项目若依框架启动失败,启动不了服务提示端口8080占用escription: Web server failed to start. Port 8080 was already in use. Action: Identify and stop the process that’s listening on port 8080 or configure this application to listen on another port-优雅草卓伊凡解决方案
1374 7
|
传感器 运维 安全
共享单车上的数字足迹:用代理IP编织隐私防护网
当你用手机扫描共享单车二维码时,设备间的数据交换远比表面复杂。骑行轨迹被分解为解锁时的基站定位、骑行中的GPS坐标、停留点的蓝牙信号和结算时的支付账户数据。这些信息通过运营商网络传输至云端,形成精确到分钟的时空画像。智能锁还记录骑行姿态,九轴传感器生成详细日志文件。然而,数据传输中存在泄漏风险,如IMEI码与IP关联导致隐私暴露。云端数据聚合则将骑行数据与其他消费行为交叉分析,提升广告转化率但威胁用户隐私。代理IP技术成为关键解决方案,通过动态IP轮换和流量混淆技术保护隐私,降低真实IP暴露率。未来,量子加密和生物特征技术将进一步影响隐私保护与商业成本的平衡。
613 1
|
运维 监控 安全
ClickHouse安全与管理:从基础到高级
【10月更文挑战第26天】在大数据时代,数据的安全性和系统的稳定性是企业成功的关键因素之一。作为一款高性能的列式数据库,ClickHouse 不仅在数据处理方面表现出色,同时也提供了多种安全和管理功能,以确保数据的安全性和系统的可靠性。本文将从我个人的角度出发,探讨如何加强 ClickHouse 的安全性以及如何进行日常运维管理。
660 2