Merge pull request gzc426#284 from hopewolf/master

gzc426 · web-flow · commit eb6d9ab8fc28 · 2018-12-03T19:47:30.000+08:00
new version
diff --git a/2018.12.04-leetcode101/Istoryforever.md b/2018.12.04-leetcode101/Istoryforever.md
@@ -0,0 +1,25 @@
+leetcode of 101
+```
+/**
+ * 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:
+    bool isSymmetric(TreeNode* p1,TreeNode * p2){
+        if((p1 == nullptr && p2!=nullptr) || (p2 == nullptr && p1!=nullptr)) return false;
+        if(p1 == nullptr && p2 == nullptr) return true;
+        if(p1->val != p2->val) return false;
+        return isSymmetric(p1->left,p2->right) && isSymmetric(p1->right,p2->left);
+        
+    }
+    bool isSymmetric(TreeNode* root) {
+        return isSymmetric(root,root);   
+    }
+};
+```
diff --git a/2018.12.05-leetcode102/Istoryforever.md b/2018.12.05-leetcode102/Istoryforever.md
@@ -0,0 +1,47 @@
+leetcode of 102
+```
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ *     int val;
+ *     TreeNode *left;
+ *     TreeNode *right;
+ *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
+ * };
+ */
+struct DataNode{
+    TreeNode * p;
+    int depth;
+};
+class Solution {
+public:
+    vector<vector<int>> levelOrder(TreeNode* root) {
+        vector<vector<int>> ans;
+        if(root == nullptr) return ans;
+        queue<DataNode> q;
+        int depth = 0;
+        q.push(DataNode{root,depth});
+        vector<int>t;
+        while(!q.empty()){
+            DataNode dn = q.front();    
+            q.pop();
+            if(depth == dn.depth){
+                t.push_back(dn.p->val);
+            }else{
+                depth = dn.depth; 
+                ans.push_back(t);
+                t.clear();
+                t.push_back(dn.p->val);
+            }      
+            if(dn.p->left != nullptr)
+               q.push(DataNode{dn.p->left,depth+1});
+            if(dn.p->right != nullptr) 
+                q.push(DataNode{dn.p->right,depth+1});
+            
+        }
+        ans.push_back(t);
+        return ans;
+        
+    }
+};
+```
diff --git a/2018.12.06-leetcode103/Istoryforever.md b/2018.12.06-leetcode103/Istoryforever.md
@@ -0,0 +1,55 @@
+leetcode of 103
+```
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ *     int val;
+ *     TreeNode *left;
+ *     TreeNode *right;
+ *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
+ * };
+ */
+struct DN{
+    TreeNode * p;
+    int depth;
+};
+class Solution {
+public:
+    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
+        vector<vector<int>> ans;
+        if(root == nullptr) return ans;
+        bool flag = true;
+        int depth = 0;
+        queue<DN> q;
+        vector<int>t;
+        q.push(DN{root,0});
+        while(!q.empty()){
+            DN dn = q.front();       
+            q.pop();
+            if(dn.depth == depth){
+                t.push_back(dn.p->val);
+            }else{
+                depth = dn.depth;
+                if(!flag) reverse(t.begin(),t.end());
+                ans.push_back(t);
+                flag=!flag;
+                t.clear();
+                t.push_back(dn.p->val);
+            }
+            
+            if(dn.p->left) q.push(DN{dn.p->left,depth+1});
+            if(dn.p->right) q.push(DN{dn.p->right,depth+1});
+         
+            if(q.empty()) 
+            {
+                if(!flag) reverse(t.begin(),t.end());
+                ans.push_back(t);
+            }
+        }
+       
+        return ans;
+        
+        
+    }
+};
+```
diff --git a/2018.12.07-leetcode104/Istoryforever.md b/2018.12.07-leetcode104/Istoryforever.md
@@ -0,0 +1,24 @@
+leetcode of 104
+```
+/**
+ * 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:
+    int maxDepth(TreeNode* root) {
+         if(root == nullptr){
+            return 0;
+        }
+        int l = maxDepth(root->left);
+        int r = maxDepth(root->right);
+        int m = l > r ? l : r;
+        return m+1;
+    }
+};
+```
diff --git a/2018.12.08-leetcode105/Istoryforever.md b/2018.12.08-leetcode105/Istoryforever.md
@@ -0,0 +1,38 @@
+leetcode of 105
+```
+/**
+ * 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:
+   
+    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder,int s,int t,int &i) {
+        if(i == preorder.size()) return nullptr;
+        int val = preorder[i++];
+        TreeNode * root = new TreeNode(val);
+        if(s >= t - 1){
+            return root;
+        }
+        int index = find(inorder.begin()+s,inorder.begin()+t,val) - inorder.begin();
+        if(index != s){
+            root->left = buildTree(preorder,inorder,s,index,i);
+        }
+        if(index != t - 1){
+            root->right = buildTree(preorder,inorder,index+1,t,i);
+        }
+        return root;
+    
+        
+    }
+    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){
+        int i=0;
+        return   buildTree(preorder,inorder,0,preorder.size(),i);
+    }
+};
+```
diff --git a/2018.12.09-leetcode106/Istoryforever.md b/2018.12.09-leetcode106/Istoryforever.md
@@ -0,0 +1,35 @@
+leetcode of 106
+```
+/**
+ * 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:
+    TreeNode * buildTree(vector<int>& inorder, vector<int>& postorder,int s,int t,int & i) {
+        if(s == t) return nullptr;
+        TreeNode * root = new TreeNode(postorder[i--]);
+        int val = root->val;
+        if(s >= t-1) return root;
+        int index = find(inorder.begin()+s,inorder.begin()+t,val) - inorder.begin();
+        if(index != t-1){
+            root->right = buildTree(inorder,postorder,index+1,t,i);
+        }
+        if(index != s){
+            root->left = buildTree(inorder,postorder,s,index,i);
+        }
+      
+        return root;
+        
+    }
+    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
+        int i = inorder.size()-1;
+        return buildTree(inorder,postorder,0,inorder.size(),i);
+    }
+};
+```
diff --git a/2018.12.10-leetcode107/Istoryforever.md b/2018.12.10-leetcode107/Istoryforever.md
@@ -0,0 +1,53 @@
+leetcode of 107
+```
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ *     int val;
+ *     TreeNode *left;
+ *     TreeNode *right;
+ *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
+ * };
+ */
+struct DNODE{
+    int depth;
+    TreeNode * p;
+    DNODE(int d,TreeNode * p){
+        this->depth = d;
+        this->p = p;
+    }
+};
+class Solution {
+public:
+    vector<vector<int>> levelOrderBottom(TreeNode* root) {
+        queue<DNODE> q;         
+        DNODE dn(0,root);
+        q.push(dn);
+        int depth = 0;
+        vector<vector<int>>ans;
+        if(root == nullptr) return ans;
+        vector<int>cur;
+        while(!q.empty()){
+            dn=q.front();
+            q.pop();
+            if(dn.p->left){
+                q.push(DNODE(dn.depth+1,dn.p->left));
+            }
+            if(dn.p->right){
+                q.push(DNODE(dn.depth+1,dn.p->right));
+            }
+            if(depth == dn.depth){
+                cur.push_back(dn.p->val);
+            }else if(depth != dn.depth){
+                ans.push_back(cur);
+                vector<int>().swap(cur);
+                cur.push_back(dn.p->val);
+                depth = dn.depth;
+            }
+        }
+        ans.push_back(cur);
+        reverse(ans.begin(),ans.end());
+        return ans;
+    }
+};
+```
