13_翻转二叉树

简介: 13_翻转二叉树

翻转二叉树

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。

示例 1:

输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]

示例 2:

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

示例 3:

输入:root = []
输出:[]

【思路】基本思想就是想要翻转二叉树,只需要把每一个节点的左右孩子交换一下就可以了。关键在于遍历顺序,前中后序应该如何选择呢?

遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。

import java.util.LinkedList;
import java.util.Queue;
/**
 * 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 {
    /*
    // 法一:BFS
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            while (levelSize-- > 0) {
                TreeNode poll = queue.poll();
                swap(poll);
                if (poll.left != null) {
                    queue.add(poll.left);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                }
            }
        }
        return root;
    }
    */
    /**
     * 方法二:
      前后序遍历都可以,中序不行,因为先左孩子交换孩子,再根交换孩子(做完后,右孩子已经变成了原来的左孩子),再右孩子交换孩子(此时其实是对原来的左孩子做交换)
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        swap(root);
        return root;
    }
        //交换左、右孩子节点
        public void swap(TreeNode root) {
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
        }
}
相关文章
|
Java 程序员 调度
【JAVA 并发秘籍】进程、线程、协程:揭秘并发编程的终极武器!
【8月更文挑战第25天】本文以问答形式深入探讨了并发编程中的核心概念——进程、线程与协程,并详细介绍了它们在Java中的应用。文章不仅解释了每个概念的基本原理及其差异,还提供了实用的示例代码,帮助读者理解如何在Java环境中实现这些并发机制。无论你是希望提高编程技能的专业开发者,还是准备技术面试的求职者,都能从本文获得有价值的见解。
186 1
|
12月前
|
消息中间件 网络协议 安全
C# 一分钟浅谈:WebSocket 协议应用
【10月更文挑战第6天】在过去的一年中,我参与了一个基于 WebSocket 的实时通信系统项目,该项目不仅提升了工作效率,还改善了用户体验。本文将分享在 C# 中应用 WebSocket 协议的经验和心得,包括基础概念、C# 实现示例、常见问题及解决方案等内容,希望能为广大开发者提供参考。
781 0
|
监控 安全 网络安全
|
弹性计算 人工智能 数据挖掘
阿里云高校计划“云工开物”解读,适合学生及高校教师参考
阿里云推出“云工开物”高校计划,向学生和教师提供优惠,旨在支持高等教育和培养科技人才。学生通过学信网认证可获300元优惠券和3折云服务器优惠;教师享5折全线产品折扣。此外,还有“极速上云”活动和各类挑战赛,促进实践和创新。
阿里云高校计划“云工开物”解读,适合学生及高校教师参考
|
监控 数据可视化 应用服务中间件
Cacti设置流量阀值实现邮件报警
Cacti设置流量阀值实现邮件报警
|
安全 网络安全 数据安全/隐私保护
网络拓扑结构入门快速介绍
网络拓扑结构入门快速介绍
|
监控 Java 微服务
SpringCloud极简入门-服务监控-Hystrix Dashboard & Turbine
Hystrix是一种服务熔断机制,其熔断降级策略有效的防止了微服务的雪崩问题,Hystrix的出现提高了微服务的可用性和健壮性,而Hystrix Dashboard则是用来监控Hystrix的熔断器状况的重要组件(又叫仪表盘),它提供了数据监控,健康状态,熔断状态,并发数量等等信息,和友好的图形化展示界面,能让使用者很好的监控和分析熔断器的状态。
594 0
|
JavaScript
Vue中嵌入原生HTML页面的方法
Vue中嵌入原生HTML页面的方法
2948 0
|
视频直播
详解!视频直播源码平台搭建开发:录制功能
视频直播源码平台的录制功能能够为用户提供更多方便、灵活性,同时也增加了直播内容的传播和价值,这也使录制功能成为布谷科技视频直播源码平台的必备功能之一。
详解!视频直播源码平台搭建开发:录制功能
|
存储 安全 Devops
开放原子开源基金会联合阿里云发布AtomGit代码协作平台
AtomGit基于阿里云云效研发的分布式多副本架构,所有存储和服务节点均为无状态设计。
837 0