LeetCode100. Same Tree（二叉树 / 模拟）

Easy
Accepted：350,919
Submissions：709,845

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

链接

https://leetcode.com/problems/same-tree

题意

给定两颗二叉树，判断他们是否相同，相同指结构相同以及结点的值相同。

题解

直接递归式判断就行。

如果存在一个结点为空，那么要求两者都为空，如果值不相同，那么返回false，然后递归判断左右子树。

代码

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL || q == NULL)
            return p == NULL && q == NULL;
        if (p->val != q->val)
            return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

// more simple

bool isSameTree(TreeNode *p, TreeNode *q) {
    if (p == NULL || q == NULL) return (p == q);
    return (p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right));
}

补充

之前做过一个判断二叉树是否同构的题目，在此贴上。

二叉树同构：给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。

考虑满二叉树同构，设节点数为n

对于二叉树的一个节点，有两种可能，要么“左左右右”匹配，要么“左右右左”匹配（左儿子右儿子）

最差情况下，$T(n) = 4T(n/2),T(1) = 1$，则$T(n) = 4(4T(n/4)) = 4^{log_2n}= n^2$，时间复杂度为$n^2$
最好情况下，$T(n) = 2T(n/2),T(1) = 1$，则$T(n) = n$，时间复杂度为$n$
平均情况下，时间复杂度为$n^2$
由于二叉树的结构，递归深度为$log_2n$，所以空间复杂度为$logn$

// AC for https://pintia.cn/problem-sets/15/problems/711

typedef int Type;
struct TreeNode
{
    Type value;
    TreeNode * leftChild;
    TreeNode * rightChild;
};

bool isomorphic(TreeNode * T1, TreeNode * T2) // 判断是否同构
{
    if (T1 == NULL || T2 == NULL) // 出现空则要求均为空
        return T1 == NULL && T2 == NULL;
    if (T1->value != T2->value) // 值不相同
        return false;
    // 左右孩子结点互换比较，一种为真即可
    return (isomorphic(T1->leftChild, T2->leftChild) && isomorphic(T1->rightChild, T2->rightChild)) ||
            (isomorphic(T1->leftChild, T2->rightChild) && isomorphic(T1->rightChild, T2->leftChild))
}

The end.
2019年3月7日星期四