题意

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
给定两棵二叉树，需要判断他们是否相等，相等的定义是结构相同且对应的值相等。

思路

根据不同类型，对二叉树的节点进行标记。例如将空节点（父节点指针为空所抽象出来的节点）记为 0 ，仅有左子树的节点记为 1 ，仅有右子树的节点记为 2 ，叶子节点记为 3 ，同时有左右子树的节点记为 4 ，使用相同的遍历算法分别遍历两个二叉树，得到节点类型序列和节点值的序列，当且仅当节点类型序列和节点值序列相等时两二叉树相等。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    void dfs(struct TreeNode* root, vector<int>& strct, vector<int>& vals)
    {
        if(root == NULL)
        {
            strct.push_back(0);
            vals.push_back(0);
            return;
        }
        vals.push_back(root->val);
        if(root->left && !root->right) strct.push_back(1);
        if(!root->left && root->right) strct.push_back(2);
        if(!root->left && !root->right) strct.push_back(3);
        if(root->left && root->right) strct.push_back(4);
        dfs(root->left, strct, vals);
        dfs(root->right, strct, vals);
    }
    bool isSameTree(TreeNode* p, TreeNode* q)
    {
        vector<int> strct_p,strct_q;
        vector<int> val_p,val_q;
        dfs(p, strct_p, val_p);
        dfs(q, strct_q, val_q);
        if(strct_p.size() != strct_q.size()) return false;
        bool ret = true;
        for(int i = 0; i < (int)strct_p.size(); i++)
        {
            if(strct_p[i] != strct_q[i] || val_p[i] != val_q[i])
            {
                ret = false;
                break;
            }
        }
        return ret;
    }
};