[C++][简单][树]判断两颗树相等

题目

思路

该题很简单，想办法将其遍历再判断就行，不过遍历的方法有很多种。

1. 常规思路：先中后遍历

先序、中序、后序遍历是最基本的遍历，这里用先序。

    void travelTree(TreeNode* tree1, TreeNode* tree2) {
        if (tree1 == nullptr || tree2 == nullptr) {
            if (tree1 != tree2) {
                this->isPair = false;
            }
            return ;
        }

        // 先序
        if (tree1->val != tree2->val) {
            this->isPair = false;
            return ;
        }
        travelTree(tree1->left, tree2->left);
        travelTree(tree1->right, tree2->right);
    }

此处的算法复杂度是：O(min(M,N))，M,N分别是树的结点数。

虽然简单，但我们应该总结下该思路。此处仅仅做了两个判断，一个是关于tree本身的，另一个是对两个结点的值进行判断的。而其他是递归的操作。

对于该题，或者是树相关的题目，我们一般思路就是递归，递归在可读性上强与循环遍历，解决问题的过程中只需要关注我们最终的目的就行了，剩下的事情就交给函数本身了。如果需要再深的分析就需要自己再多琢磨一下了。

而该代码实现中，新建了一个函数，为了展现常规的思路，我们还可以在解决问题的函数中使用递归解决本题。

2. 代码优化->深度优先搜索

深度优先搜索(DFS)是树和图中的关键遍历方法，顾名思义，就是从一个结点出发，知道到达该结点的最后，再往回走。所谓的深度优先，可以理解为一条路走到底，再去走另外一条路。在树当中，就是一个分支走到底，然后再返回到另一个分支上去。

如果理解到位了，我们就可以继续写代码了:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 首先判空 ：： 递归的返回条件
        if (p == nullptr || q == nullptr) {
            return p == q;
        }

        // 非空必有其值 ：： 递归的返回条件
        // 而一旦遇到值不相等，撤
        if (p->val != q->val) {
            return false;
        }

        // 值相等，往下走
        return isSameTree(p->left, q->left) /* 左边这个支路 */ /* 由于递归，这条支路会一路到底，深度优先 */ &&
            isSameTree(p->right, q->right); /* 右边支路 */

        // 仅仅考虑需要解决的问题，p和q对应的结点存在的值是否相等，遍历交给递归去做。
    }
};

同样，此处使用了递归，只考虑核心的问题，对应节点的值是否相等，其他交给函数本身的特性。

虽然理论上与前者的时间复杂度一致，但实际执行较快。

除了深度优先，我们也听说过广度优先，那么如何实现呢？

2. 再来一次->广度优先

所谓的广度优先(BFS)，在树当中，就是每条支路都走。一个二叉树，有两条路，那么我左右走一遍，再回去，下一层。就是层次优先，参照完全二树标点的时候。比如一栋楼，我先走完这一层，再往上走。

实现起来比较麻烦，解决这道题，如果没有必要，广度优先是不需要使用的。

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 确保非空
        if (p == nullptr || q == nullptr) {
            return p == q;
        }

        // BFS
        // 需要记录每一层的结点 本处使用对列
        queue<TreeNode *> layerP, layerQ;

        layerP.push(p), layerQ.push(q);

        // 获取队列长度 记录每一层队列的长度
        auto sizeP = layerP.size(),
            sizeQ = layerQ.size();

        // 层都不空 进入循环
        while(!layerP.empty() && !layerQ.empty()) {
            // 再获取size
            sizeP = layerP.size(),
            sizeQ = layerQ.size();

            // 所在的一层，结点数不一值
            if (sizeP != sizeQ) {
                return false;
            }

            // 遍历
            while(sizeP-- && sizeQ--) {
                // 获取节点
                TreeNode* pNode = layerP.front();
                TreeNode* qNode = layerQ.front();
                // 弹出
                layerP.pop(), layerQ.pop();

                // 判断
                if (pNode->val != qNode->val) {
                    return false;
                }

                // 左右子树
                auto pLeft = pNode->left,
                    pRight = pNode->right, 
                    qLeft = qNode->left,
                    qRight = qNode->right;

                // 若下一层不等，则不需要再对比
                if (pLeft == nullptr ^ qLeft == nullptr) {
                    return false;
                }  
                if (pRight == nullptr ^ qRight == nullptr) {
                    return false;
                }

                // 输入
                // layerP 存储左子树 layerQ 存右子树 顺序不能乱
                if (pLeft != nullptr) {
                    layerP.push(pLeft);
                }
                if (pRight != nullptr) {
                    layerP.push(pRight);
                }
                if (qLeft != nullptr) {
                    layerQ.push(qLeft);
                }
                if (qRight != nullptr) {
                    layerQ.push(qRight);
                }
            }
        }

        // 已经遍历完成 确保队列中再无元素
        return layerP.empty() && layerQ.empty();
    }
};

思路很简单，就找个方法把当前层的东西记住，然后就逐个比较。

总结

对于树的比较，可以扩展到很多相对应的题目，其核心解题思路就是BFS和DFS，先中后遍历。有这三样，树的问题基本解决。再高的难度也不在话下了。

而找到了核心问题，将繁杂的问题化为主要解决的问题，再借助递归，可读性高且容易理解。