[LeetCode] 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.

思考：

和Balanced Binary Tree那题很像。定义T(p)为以p为根的树，T(p) = T(q)需要符合两个条件：

(1) p和q等价，这里的等价有两种情况：p = q = NULL，或p、q都不为NULL且p->val = q->val。反过来说当p和q中只有一个为NULL，或者p->val != q->val时p和q不等价。

(2) 如果p和q都不为NULL，则要求T(p->left) = T(q->left)且T(p->right) = T(q->right)。

想清楚以上两点，基本上就秒杀了。

1 2 3 4 5 6 7 8 9

class Solution { public: bool isSameTree(TreeNode *p, TreeNode *q) { if(!p && !q) return true; if((!p && q) || (p && !q)) return false; if(p->val != q->val) return false; return isSameTree(p->left,q->left) && isSameTree(p->right,q->right); } };