首页 > 代码库 > 38. Same Tree && Symmetric Tree
38. Same Tree && Symmetric 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 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 == NULL && q) || (p && q == NULL)) return false; if(p == NULL && q == NULL) return true; if(p->val != q->val) return false; return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); }};
Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1 / 2 2 / \ / 3 4 4 3
But the following is not:
1 / 2 2 \ 3 3
Note: Bonus points if you could solve it both recursively and iteratively.
思想： 构造其镜像树。
1. 递归。用 Same Tree方法判断即可。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */TreeNode* getMirror(TreeNode *root) { if(root == NULL) return NULL; TreeNode *p = new TreeNode(root->val); p->left = getMirror(root->right); p->right = getMirror(root->left); return p;}bool isSymmetricCore(TreeNode *root, TreeNode *root2) { if((!root && root2) || (root && !root2)) return false; if(!root && !root2) return true; if(root->val != root2->val) return false; return isSymmetricCore(root->left, root2->left) && isSymmetricCore(root->right, root2->right);}class Solution {public: bool isSymmetric(TreeNode *root) { TreeNode *mirrorTree = getMirror(root); return isSymmetricCore(root, mirrorTree); }};2. 迭代。两棵树相同方法遍历即可。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */TreeNode* getMirror(TreeNode *root) { if(root == NULL) return NULL; TreeNode *p = new TreeNode(root->val); p->left = getMirror(root->right); p->right = getMirror(root->left); return p;}bool pushChildNode(TreeNode *p1, TreeNode *p2, queue<TreeNode*> & qu, queue<TreeNode*>& qu2) { if(p1->left && p2->left) { qu.push(p1->left); qu2.push(p2->left); } else if(p1->left || p2->left) return false; if(p1->right && p2->right) { qu.push(p1->right); qu2.push(p2->right);} else if(p1->right || p2->right) return false; return true;}class Solution {public: bool isSymmetric(TreeNode *root) { if(root == NULL) return true; TreeNode *mirrorTree = getMirror(root); queue<TreeNode*> que1; queue<TreeNode*> que2; que1.push(root); que2.push(mirrorTree); while(!que1.empty() && !que2.empty()) { TreeNode *p1 = que1.front(), *p2 = que2.front(); que1.pop(); que2.pop(); if(p1->val != p2->val) return false; if(!pushChildNode(p1, p2, que1, que2)) return false; } if(!que1.empty() || !que2.empty()) return false; return true; }};
38. Same Tree && Symmetric Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。