Skip to content

LeetCode 100 相同的树 DFS#

目录#

1. 题目描述#

1.1. Limit#

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description#

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

1.5. Sample Input#

输入:       1         1
          / \       / \
         2   3     2   3

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

1.6. Sample Output#

输出: true

1.5. Sample Input#

输入:      1          1
          /           \
         2             2

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

1.6. Sample Output#

输出: false

1.8. Source#

LeetCode 100 相同的树

2. 解读#

DFS，先判断节点是否为空，然后比较左右节点的值是否相等。

3. 代码#

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q)
    {
        bool leftFalg = false, rightFlag = false;
        // 若其一为空
        if (p == nullptr || q == nullptr) {
            // 判断是否都为空
            if (p == q) {
                return true;
            } else {
                return false;
            }

        } else {
            // 若不为空
            if (p->val != q->val) {
                // 若值不相等，返回false
                return false;
            }
            // 若值相等，继续判定左右节点
            leftFalg = isSameTree(p->left, q->left);
            rightFlag = isSameTree(p->right, q->right);

            if (leftFalg && rightFlag) {
                return true;
            } else {
                return false;
            }
        }
    }
};

联系邮箱：curren_wong@163.com

CSDN：https://me.csdn.net/qq_41729780

知乎：https://zhuanlan.zhihu.com/c_1225417532351741952

公众号：复杂网络与机器学习

欢迎关注/转载，有问题欢迎通过邮箱交流。

二维码

Back to top