Shinkai005
V1
2022/02/12阅读:31主题:红绯
# 【leetcode】226. 翻转二叉树
【leetcode】226. 翻转二叉树
题目描述
题目思路
-
先翻转左右字数,再将子树换个位置 -
符合分解合的特性 -
可以使用分而治之来做
个人题解
/**
* 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) 迭代也会消耗空间,主要是运行堆栈, 因此,这道题的消耗空间就是迭代的堆栈的高度
作者介绍
Shinkai005
V1
公众号:深海笔记Shinkai