MENU

LeetCode100. Same Tree(二叉树 / 模拟)

2019 年 03 月 07 日 • 阅读: 849 • LeetCode阅读设置

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日 星期四