101. Symmetric Tree

LeetCode easy original: C# #csharp #easy #leetcode #recursion #tree #two-pointers

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

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

Example:

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

Output: true

C# solution

matched/original

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++ solution

auto-draft, review before submit

#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 solution

matched/original

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 solution

matched/original

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 solution

matched/original

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 solution

matched/original

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️⃣

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

2️⃣

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

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

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

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

3️⃣

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

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

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.