LeetCode | 100.相同的树

这次来写一下 LeetCode 的第 100 题，相同的树。

题目描述

题目直接从 LeetCode 上截图过来，题目如下：

image

上面的题就是相同的树题目的截图，同时 LeetCode 会根据选择的语言给出了一个类的定义或者函数的定义，然后在其中实现相同的树的解题过程。这次我使用 C 语言来进行完成。

C 语言给出的函数定义如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
}

通过函数定义可以看出，isSameTree 函数的参数是两个双向链表，然后返回值是一个布尔类型的值，我们要做的就是把两个树进行遍历比对即可。

问题分析

从阅读问题来看，题目的参数是两个以链式存储的树型结构，且是一个二叉树。那么要比较两棵树是否相同，就需要遍历二叉树上的每个节点上的值是否相同，相同则为相同的树，否则就不是相同的树。

对于二叉树的遍历，常见的方法有前序遍历、中序遍历、后续遍历和层次遍历，对于层次遍历而言，需要增加额外的数据结构去支持它。因此，我们考虑使用其他三种遍历方式，而我认为使用前序遍历比较好。原因是，前序遍历可以提早的进行节点上存储的值的比较，而中需遍历和后序遍历是先找到左节点上的值进行比较。拿中序遍历来说，从根节点开始找到最左面的节点进行比较，假如根节点的左子树是相同的，而根节点的值就是不同的，那么就浪费了时间和空间。后序遍历不但要先遍历左子树，遍历完左子树还要遍历右子树，最后才遍历根，效率会更慢。因此，我选择了前序遍历的方式。

前序遍历也叫先根遍历，也就是从树的根节点开始，然后是左子树，再然后是右子树这样一个顺序。举例如下。

image.gif

我在图中画的节点中的值，表示的前序遍历的遍历顺序。而不是表示节点中的值。

代码实现

C 语言的代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if (p == NULL && q == NULL) {
        return true;
    }


    if ((p == NULL && q != NULL) || (p != NULL && q == NULL) || (p->val != q->val)) {
        return false;
    }


    // 遍历左子树
    // p和q同时没有左子树时，遍历右子树
    if (p->left == NULL && q->left == NULL) {


    } else {
        // p和q同时都有左子树，则判断值的节点是否相同
        if (p->left != NULL && q->left != NULL) {
            if (!isSameTree(p->left, q->left)) {
                return false;
            }
        } else {
            // 该分支的情况是
            // p->left != NULL && q->left == NULL
            // 或者是 p->left == NULL && q->left != NULL
            return false;
        }
    }

    // 遍历右子树
    // p和q同时没有右子树，返回真
    if (p->right == NULL && q->right == NULL) {
        return true;
    }


    // p和q同时都有右子树，则判断值的节点是否相同
    if (p->right != NULL && q->right != NULL) {
        if (!isSameTree(p->right, q->right)) {
            return false;
        }
    } else {
        // 该分支的情况是
        // p->right != NULL && q->right == NULL
        // 或者是 p->right == NULL && q->right != NULL
        return false;
    }


    return true;
}

代码中有了详细的注释，主要就是对二叉树的一个遍历，还有每个节点值的比较，如果节点上的值相同，就继续遍历，如果节点上的值不同，就直接返回 false，所有的节点都相同就返回 true。

在我写代码的时候，当某个节点的左子树都不存在时，需要继续遍历右子树，而不是直接返回。这一点在逻辑上好理解，但是写代码的时候我还是花费了一点时间。

提交结果

在写完代码后，点击右下角的 “执行代码”，然后观察 “输出” 和 “预期结果” 是否一致，一致的话就点击 “提交” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体，如果所有的测试用例都通过了，那么就会给出 “通过” 的字样，如果没有通过，会给出失败的那一组测试用例，我们可以根据给出的测试用例来继续修改代码。我们的代码提交后的截图如下：

image