首页 > 代码库 > [Leetcode][Tree][Symmetric Tree]
[Leetcode][Tree][Symmetric Tree]
如果按层次遍历，存下每一层的点，会MLE。
1、递归版本：关键还是子问题的划分。
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 symmetric(TreeNode * leftnode, TreeNode * rightnode) {13 if (leftnode == NULL && rightnode == NULL) {14 return true;15 }16 if (leftnode == NULL || rightnode == NULL) {17 return false;18 }19 if (leftnode->val != rightnode->val) {20 return false;21 }22 return symmetric(leftnode->left, rightnode->right) &&23 symmetric(leftnode->right, rightnode->left);24 }25 bool isSymmetric(TreeNode *root) {26 if (root == NULL) {27 return true;28 } else {29 return symmetric(root->left, root->right);30 }31 }32 };
2、迭代版本：思路很巧妙，不看题解自己真的想不出来。。对自己的智商好捉急。。
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 isSymmetric(TreeNode *root) {13 queue<TreeNode *> q;14 if (root == NULL) {15 return true;16 } else {17 q.push(root->left);18 q.push(root->right);19 }20 while (!q.empty()) {21 TreeNode * n1 = q.front();22 q.pop();23 TreeNode * n2 = q.front();24 q.pop();25 if (n1 == NULL && n2 == NULL) {26 continue;27 }28 if (n1 == NULL || n2 == NULL) {29 return false;30 }31 if (n1->val != n2->val) {32 return false;33 }34 q.push(n1->left);35 q.push(n2->right);36 q.push(n1->right);37 q.push(n2->left);38 }39 return true;40 }41 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。