前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >翻转二叉树

翻转二叉树

原创
作者头像
_kyle
修改于 2020-12-14 06:10:07
修改于 2020-12-14 06:10:07
26500
代码可运行
举报
文章被收录于专栏:kyle的专栏kyle的专栏
运行总次数:0
代码可运行

题目描述

翻转一棵二叉树。

示例:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:

     4
   /   \
  2     7
 / \   / \
1   3 6   9
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输出:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

备注:

这个问题是受到 Max Howell 的 原问题 启发的 :

谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。

解题思路

广度优先搜索

使用队列,当队列中有元素时,则对依次出列,并对当前元素通过中间变量进行左右交换,若交换后的元素存在,则再进入队列。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
const invertTree = function(root) {
    if (!root) return null
    const queue = [root]

    while(queue.length){
        let node = queue.shift()
        let temp = node.left
        node.left = node.right
        node.right = temp

        if (node.left)
            queue.push(node.left)
        if (node.right)
            queue.push(node.right)
    }

    return root
};
  • 简化代码
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
const invertTree = function(root) {
    if (!root) return null
    const queue = [root]

    while(queue.length){
        let node = queue.shift();
        [node.left, node.right] = [node.right, node.left]
        
        if (node.left)
            queue.push(node.left)           
        if (node.right)
            queue.push(node.right)  
    }

    return root
};

递归

当前函数进行左右节点交换,若左节点或右节点存在,则再次对存在节点调用invertTree函数。需要注意的是当根节点为空时,则直接返回null。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
const invertTree = function(root) {
    if (!root) return null;
    [root.left, root.right] = [root.right, root.left]

    if (root.left) invertTree(root.left)
    if (root.right) invertTree(root.right)

    return root
};

题目来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/invert-binary-tree

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
    • 示例:
  • 备注:
  • 解题思路
    • 广度优先搜索
  • 递归
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档