Shinkai005

V1

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

# 【leetcode】100.相同的树(2)

【leetcode】100.相同的树(2)

image-20220212085245101
image-20220212085245101

题目描述

image-20211212174230529
image-20211212174230529

题目思路

两个树:根节点的值相同,左子树相同,右子树相同.

分而治之可以用

个人题解

/**
 * 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} p
 * @param {TreeNode} q
 * @return {boolean}
 */

var isSameTree = function (p, q{
    /**
     分:获取两个树的左子树和右子树
     解:递归的判断左右子树是否相同
     合:如果上述相同根也形同,树就相同
     */

    if (!p && !q) return true;
    else if (!p && q) return false;
    else if (!q && p) return false;

    if ((p && q && p.val === q.val) &&
        isSameTree(p.left, q.left) &&
        isSameTree(p.right, q.right)
    ) {
        return true;
    }
    return false;
};

总结优化

在if判断里迭代感觉好丑,但是让我改又不太会...返回值再判断也好不到哪里去..

时间复杂度(time complexity)

O(n) 迭代n次

空间复杂度(space complexity)

O(n) 都写在左子树

分类:

前端

标签:

JavaScript

作者介绍

Shinkai005
V1

公众号:深海笔记Shinkai