LeetCode100—Same Tree

原题

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.

Subscribe to see which companies asked this question

判断两棵树是否相同。

分析

两棵树不同只有两种情况：
1. 两棵树的节点数不相同，那么肯定不是相同的树
2. 两棵树对应节点位置的值不相同（遍历出来的结果）

根据上述两个条件，如果其中一棵树先递归返回，直接返回false，同一方向递归深度两棵树根节点的值不同，返回false，如果两棵树同时递归返回，且不出现上述两个条件则返回false。分别对两棵树的左子树右子树进行判断。

代码

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL && q == NULL)
            return true;
        if (p==NULL || q==NULL)//节点个数不同
            return false;
        if (p->val != q->val)//节点个数相同，值不同
            return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};