• Same Tree

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 values. 题目翻译:
给两棵树，写一个函数来判断这两棵树是否相同. 我们判定一棵树是否相同的条件为这两棵树的结构相同，并且每个节点的值相同. 解题思路:
这道题中规中矩，很简单，我们直接用DFS前序遍历这两棵树就可以了. 时间复杂度分析:
因为是DFS, 所以时间复杂度为O(n) 代码如下: 1. / 2. * Definition for binary tree 3. * struct TreeNode { 4. * int val; 5. * TreeNode left; 6. * TreeNode right; 7. * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8. * }; 9. / 10. class Solution { 11. public: 12. bool isSameTree(TreeNode p, TreeNode *q) { 13. if(p == NULL && q == NULL) 14. return true; 15. else if(p == NULL || q == NULL) 16. return false; 17. if(p->val == q->val) 18. { 19. bool left = isSameTree(p->left, q->left); 20. bool right = isSameTree(p->right,q->right); 21. return left&&right; 22. } 23. return false; 24. } 25. };