首页 > 代码库 > 【LeetCode】Symmetric Tree (2 solutions)
【LeetCode】Symmetric Tree (2 solutions)
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、left对应right
2、left->left对应right->right
3、left->right对应right->left
解法一：递归
/** * 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 isSymmetric(TreeNode *root) { if(root == NULL) return true; else return Helper(root->left, root->right); } bool Helper(TreeNode* left, TreeNode* right) { if(!left && !right) return true; else if(!left && right) return false; else if(left && !right) return false; else { if(left->val != right->val) return false; else {//recursion bool partRes1 = Helper(left->left, right->right); bool partRes2 = Helper(left->right, right->left); return partRes1 && partRes2; } } }};
解法二：非递归
使用两个队列，对左右子树分别进行层次遍历。
进队时的对应元素比较即可。
/** * 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 isSymmetric(TreeNode *root) { if(root == NULL) return true; else if(root->left && !root->right) return false; //right is NULL else if(!root->left && root->right) return false; //left is NULL else if(!root->left && !root->right) return true; //both NULL else { if(root->left->val != root->right->val) return false; else { queue<TreeNode*> lq; queue<TreeNode*> rq; lq.push(root->left); rq.push(root->right); while(!lq.empty() && !rq.empty()) { TreeNode* lfront = lq.front(); lq.pop(); TreeNode* rfront = rq.front(); rq.pop(); //lfront->left vs. rfront->right if(lfront->left && !rfront->right) return false; //rfront->right is NULL else if(!lfront->left && rfront->right) return false; //lfront->left is NULL else if(!lfront->left && !rfront->right) ; //both NULL else { if(lfront->left->val != rfront->right->val) return false; else { lq.push(lfront->left); rq.push(rfront->right); } } //lfront->right vs. rfront->left if(lfront->right && !rfront->left) return false; //rfront->left is NULL else if(!lfront->right && rfront->left) return false; //lfront->right is NULL else if(!lfront->right && !rfront->left) ; //both NULL else { if(lfront->right->val != rfront->left->val) return false; else { lq.push(lfront->right); rq.push(rfront->left); } } } return true; } } }};
【LeetCode】Symmetric Tree (2 solutions)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。