Shinkai005

V1

2022/02/12阅读:31主题:红绯

# 【leetcode】226. 翻转二叉树

【leetcode】226. 翻转二叉树

image-20220212085245101
image-20220212085245101

题目描述

image-20211212171207103
image-20211212171207103

题目思路

  1. 先翻转左右字数,再将子树换个位置
  2. 符合分解合的特性
  3. 可以使用分而治之来做

个人题解

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */

var invertTree = function (root{
    /**
     1. 分: 获取左右子树
     2. 解: 递归地翻转左右子树
     3. 合: 将翻转后的左右子树换个位置放到根节点上
     */

    const rec = (node) => {
        if (!node) return null;
        rec(node.left);
        rec(node.right);
        [node.left, node.right] = [node.right, node.left];
    }
    rec(root);
    return root;
};

总结优化

在对象中,value 可以计算的

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */

var invertTree = function (root{
    /**
     1. 分: 获取左右子树
     2. 解: 递归地翻转左右子树
     3. 合: 将翻转后的左右子树换个位置放到根节点上
     */

    if(!root) return null;
    return {
        val: root.val,
        left: invertTree(root.right),
        right: invertTree(root.left)
    }
};

性能没什么变化,但是可读性感觉也没有好很多. 所以我感觉俩代码都行.

时间复杂度(time complexity)

O(n)

空间复杂度(space complexity)

O(H) 迭代也会消耗空间,主要是运行堆栈, 因此,这道题的消耗空间就是迭代的堆栈的高度

分类:

前端

标签:

JavaScript

作者介绍

Shinkai005
V1

公众号:深海笔记Shinkai