update

cshanbo · May 10, 2017 · d16825c · d16825c
1 parent 7fa5bce
commit d16825c
Show file tree

Hide file tree

Showing 3 changed files with 61 additions and 1 deletion.
diff --git a/543.diameter_of_binary_tree.cpp b/543.diameter_of_binary_tree.cpp
@@ -0,0 +1,30 @@
+//coding:utf-8
+/***********************************************************
+Program: 
+Description: Typical DFS solution
+Shanbo Cheng: cshanbo@gmail.com
+Date: 2017-03-26 14:29:19
+Last modified: 2017-03-26 14:29:43
+GCC version: 4.9.3
+***********************************************************/
+
+class Solution {
+public:
+    int maxdiadepth = 0;
+
+    int dfs(TreeNode* root){        
+        if(root == NULL) return 0;
+
+        int leftdepth = dfs(root->left);
+        int rightdepth = dfs(root->right);
+
+        if(leftdepth + rightdepth > maxdiadepth) maxdiadepth = leftdepth + rightdepth;
+        return max(leftdepth +1, rightdepth + 1);     
+    }
+
+    int diameterOfBinaryTree(TreeNode* root) {        
+        dfs(root);
+
+        return maxdiadepth;
+    }
+};
diff --git a/557.reverse_words_in_a_string.cpp b/557.reverse_words_in_a_string.cpp
@@ -1,4 +1,13 @@
-class Solution {
+//coding:utf-8
+/***********************************************************
+Program: 557
+Description: 
+Shanbo Cheng: cshanbo@gmail.com
+Date: 2017-04-14 18:59:53
+Last modified: 2017-04-14 19:00:00
+GCC version: 4.9.3
+***********************************************************/
+
 public:
     string reverseWords(string s) {
         for (int i = 0; i < s.length(); i++) {

diff --git a/572.subtree_of_another_tree.cpp b/572.subtree_of_another_tree.cpp
@@ -0,0 +1,21 @@
+//coding:utf-8
+/***********************************************************
+Program: Subtree of another tree
+Description: Standard dfs solution
+Shanbo Cheng: cshanbo@gmail.com
+Date: 2017-05-10 09:48:57
+Last modified: 2017-05-10 09:51:51
+GCC version: 4.9.3
+***********************************************************/
+
+class Solution {
+public:
+    bool isSubtree(TreeNode* s, TreeNode* t) {
+        return !t || s && (same(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t));
+    }
+
+private:
+    bool isSameTree(TreeNode* s, TreeNode* t) {
+        return !s ? !t : t && s->val == t->val && isSameTree(s->left, t->left) && isSameTree(s->right, t->right);
+    }
+};