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 };