【leetcode】226. 翻转二叉树

题目描述

题目思路

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) 迭代也会消耗空间,主要是运行堆栈, 因此,这道题的消耗空间就是迭代的堆栈的高度