Loading...
墨滴

Shinkai005

2021/12/12  阅读:50  主题:红绯

【leetcode】101.对称二叉树

【leetcode】101.对称二叉树

题目描述

image-20211212181723888
image-20211212181723888

题目思路

转换为:左右字数是否镜像

符合分而治之思想

个人题解

/**
 * 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 {boolean}
 */

var isSymmetric = function (root{
    /**
     分:获取两个树的左子树和右子树
     解:递归地判断树1的左子树和树2的右子树是否镜像,树1的右子树和数2的左子树是否镜像.
     合:上述成立,根节点相同则两个树镜像
     */

    if (!root) return true;
    const isMirror = (l, r) => {
        if (!l && !r) return true;
        if ((l && r && l.val === r.val) &&
            isMirror(l.left, r.right) &&
            isMirror(l.right, r.left)) {
            return true;
        }
        return false;
    }
    return isMirror(root.left, root.right);
};

时间复杂度(time complexity)

O(n)

空间复杂度(space complexity)

O(n)

Shinkai005

2021/12/12  阅读:50  主题:红绯

作者介绍

Shinkai005