首页 > 代码库 > LeetCode--Combination Sum
LeetCode--Combination Sum
一开始的思路是:中序遍历+判断遍历后的数组,时间空间都不是最优
果然超时了
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 vector<int> inorder;14 stack<TreeNode*> s;15 TreeNode *cur = root;16 while(cur != NULL || !s.empty()){17 while(cur != NULL){18 s.push(cur);19 cur = cur->left;20 }21 cur = s.top();22 inorder.push_back(cur->val);23 s.pop();24 cur = cur->right;25 }26 if(inorder.size()%2 != 0){27 int l = 0;28 int r = inorder.size()-1;29 while(l < r){30 if(inorder[l] != inorder[r]){31 return false;32 }33 }34 return true;35 }36 else{37 return false;38 }39 }40 };
这题其实考查递归的:
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 if(root == NULL)14 return true;15 return Recursive(root->left,root->right);16 }17 bool Recursive(TreeNode *a,TreeNode *b){18 if(a==NULL && b==NULL)return true;19 if(!a || !b)return false;20 if(a->val != b->val)return false;21 return Recursive(a->left,b->right)&&Recursive(a->right,b->left);22 }23 };
面试的时候如果需要改成迭代呢?
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 if(root == NULL)14 return true;15 return Iterative(root);16 }17 bool Iterative(TreeNode *root){18 stack<TreeNode*> s1;19 stack<TreeNode*> s2;20 s1.push(root->left);21 s2.push(root->right);22 while(!s1.empty() && !s2.empty()){23 TreeNode *tmp1 = s1.top();24 s1.pop();25 TreeNode *tmp2 = s2.top();26 s2.pop();27 if((tmp1==NULL && tmp2!=NULL)||(tmp1!=NULL && tmp2==NULL))28 return false;29 if(tmp1!=NULL && tmp2!=NULL){30 if(tmp1->val!=tmp2->val)return false;31 s1.push(tmp1->left);32 s1.push(tmp1->right);33 s2.push(tmp2->right);34 s2.push(tmp2->left);35 }36 }37 return true;38 }39 };
LeetCode--Combination Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。