LeetCode 101.对称二叉树 - JavaScript

心谭博客

发布于 2020-04-21 10:45:33

3710

发布于 2020-04-21 10:45:33

文章被收录于专栏：YuanXin

题目描述：给定一个二叉树，检查它是否是镜像对称的。

题目分析

下面这种二叉树就是镜像对称的，符合题目要求：

解法 1：递归检查

根据题目“对称”的定义，递归过程如下：

对称节点的 val 是否相同
依次递归对称节点的 left1 和 right2、right1 和 left2（结合上面的例子更好理解）

代码实现如下：

// ac地址：https://leetcode-cn.com/problems/symmetric-tree/
// 原文地址：https://xxoo521.com/2020-02-16-symmetric-tree/

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (!root) return true;

    return __isSymmetric(root.left, root.right);
};

function __isSymmetric(t1, t2) {
    if (!t1 && !t2) return true;
    if (!t1 || !t2) return false;

    return (
        t1.val === t2.val &&
        __isSymmetric(t1.left, t2.right) &&
        __isSymmetric(t1.right, t2.left)
    );
}

时间复杂度是 O(N)，空间复杂度是 O(N)。因为最坏情况下，树是线性的。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-02-16，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法