首页 > 代码库 > 【LeetCode】Same Tree (2 solutions)
【LeetCode】Same Tree (2 solutions)
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.
解法一：递归
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool isSameTree(TreeNode *p, TreeNode *q) { if(!p && !q) return true; else if(!p && q) return false; else if(p && !q) return false; else { if(p->val != q->val) return false; else return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } }};
解法二：非递归
建立两个队列分别进行层次遍历，进队时检查对应点是否相等
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool isSameTree(TreeNode *p, TreeNode *q) { if(!p && !q) return true; else if(!p && q) return false; else if(p && !q) return false; else { if(p->val != q->val) return false; else { queue<TreeNode*> lq; queue<TreeNode*> rq; lq.push(p); rq.push(q); while(!lq.empty() && !rq.empty()) { TreeNode* lfront = lq.front(); TreeNode* rfront = rq.front(); lq.pop(); rq.pop(); if(!lfront->left && !rfront->left) ;// null else if(!lfront->left && rfront->left) return false; else if(lfront->left && !rfront->left) return false; else { if(lfront->left->val != rfront->left->val) return false; else { lq.push(lfront->left); rq.push(rfront->left); } } if(!lfront->right && !rfront->right) ;// null else if(!lfront->right && rfront->right) return false; else if(lfront->right && !rfront->right) return false; else { if(lfront->right->val != rfront->right->val) return false; else { lq.push(lfront->right); rq.push(rfront->right); } } } return true; } } }};
【LeetCode】Same Tree (2 solutions)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。