101. Symmetric Tree

LeetCode easy оригинал: C# #csharp #easy #leetcode #recursion #tree #two-pointers

LeetCode Static

Дан корень бинарного дерева. Проверьте, является ли это дерево зеркальным отражением самого себя (то есть симметричным относительно своего центра).

Пример:

Input: root = [1,2,2,3,4,4,3]

Output: true

C# решение

сопоставлено/оригинал

public class Solution {
    public bool IsSymmetric(TreeNode root) {
        return IsMirror(root, root);
    }
    public bool IsMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null)
            return true;
        if (t1 == null || t2 == null)
            return false;
        return (t1.val == t2.val) && IsMirror(t1.right, t2.left) &&
               IsMirror(t1.left, t2.right);
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool IsSymmetric(TreeNode root) {
        return IsMirror(root, root);
    }
    public bool IsMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null)
            return true;
        if (t1 == null || t2 == null)
            return false;
        return (t1.val == t2.val) && IsMirror(t1.right, t2.left) &&
               IsMirror(t1.left, t2.right);
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    public boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (
            (t1.val == t2.val) &&
            isMirror(t1.right, t2.left) &&
            isMirror(t1.left, t2.right)
        );
    }
}

JavaScript решение

сопоставлено/оригинал

var isSymmetric = function (root) {
    return isMirror(root, root);
};
var isMirror = function (t1, t2) {
    if (!t1 && !t2) return true;
    if (!t1 || !t2) return false;
    return (
        t1.val === t2.val &&
        isMirror(t1.right, t2.left) &&
        isMirror(t1.left, t2.right)
    );
};

Python решение

сопоставлено/оригинал

class Solution:
    def isSymmetric(self, root):
        return self.isMirror(root, root)

    def isMirror(self, t1, t2):
        if t1 is None and t2 is None:
            return True
        if t1 is None or t2 is None:
            return False
        return (
            (t1.val == t2.val)
            and self.isMirror(t1.right, t2.left)
            and self.isMirror(t1.left, t2.right)
        )

Go решение

сопоставлено/оригинал

func isSymmetric(root *TreeNode) bool {
    return isMirror(root, root)
}

func isMirror(t1 *TreeNode, t2 *TreeNode) bool {
    if t1 == nil && t2 == nil {
        return true
    }
    if t1 == nil || t2 == nil {
        return false
    }
    return (t1.Val == t2.Val) && 
           isMirror(t1.Right, t2.Left) &&
           isMirror(t1.Left, t2.Right)
}

Algorithm

1️⃣

Дерево симметрично, если левое поддерево является зеркальным отражением правого поддерева.

2️⃣

Следовательно, вопрос заключается в том, когда два дерева являются зеркальным отражением друг друга?

Два дерева являются зеркальным отражением друг друга, если:

- Их корни имеют одинаковое значение.

- Правое поддерево каждого дерева является зеркальным отражением левого поддерева другого дерева.

3️⃣

Это похоже на человека, смотрящего в зеркало. Отражение в зеркале имеет ту же голову, но правая рука отражения соответствует левой руке настоящего человека и наоборот.

Вышеописанное объяснение естественным образом превращается в рекурсивную функцию.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.