leetcode 随笔 Symmetric Tree

本文主要是介绍leetcode 随笔 Symmetric Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Symmetric Tree

这个题说难不难，第一思路还是广度优先遍历，广度优先遍历需要一个数据结构去存储下次需要遍历的节点，加上这题的要求，可以选择申请两个数据结构，一个专门存左节点一个专门存右节点，代码稍微乱了点，但是思路简单

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:vector<TreeNode*> lefts;vector<TreeNode*> rights;bool isSymmetric(TreeNode* root) {if (lefts.empty() && rights.empty()){if (root == nullptr)return true;else{lefts.push_back(root->left);rights.push_back(root->right);return go();}}}bool go(){if (lefts.empty() && rights.empty()){return true;}else{vector<TreeNode*> tmp;vector<TreeNode*> temp;int n = lefts.size() - 1;for (int i = 0; i <= n; i++){if (lefts[i] == nullptr&&rights[n - i] == nullptr){continue;}else if (lefts[i] != nullptr&&rights[n - i] != nullptr){if (lefts[i]->val != rights[n - i]->val)return false;continue;}else{return false;}}for (int i = 0; i <= n; i++){if (lefts[i] != nullptr){tmp.push_back(lefts[i]->left);temp.push_back(lefts[i]->right);}if (rights[i] != nullptr){tmp.push_back(rights[i]->left);temp.push_back(rights[i]->right);}}lefts = tmp;rights = temp;return go();}}
};

这个runtime是9ms

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

紧接着我看了一下discuss，发现了一个深度优先搜索的办法，确实巧妙，而且我也确实没想到，这里学习一下。

class Solution {
public:bool isSymmetric(TreeNode* root) {if (root == nullptr)return true;return go(root->left, root->right);}bool go(TreeNode* l,TreeNode* r){if (l == nullptr&&r == nullptr)return true;if (l != nullptr&&r != nullptr){if (l->val == r->val)return go(l->left, r->right) && go(l->right, r->left);}return false;}
};

其实思路就是递归函数每次传递两个节点，这两个节点恰恰是需要对比的两个"镜像"节点。

代码巧妙，无需多言。o(￣▽￣)ｄ

这篇关于leetcode 随笔 Symmetric Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---