2017.03.12

Jason-LLL · Jason-LLL · commit d6ec2cd457ce · 2017-03-12T23:10:59.000+08:00
diff --git a/BalancedBinaryTree.cpp b/BalancedBinaryTree.cpp
@@ -0,0 +1,31 @@
+/**
+ * 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 isBalanced(TreeNode* root) {
+if(root==NULL)
+return true;
+int left=height(root->left);
+int right = height(root->right);
+if(abs(left-right)>1)
+return false;
+else
+return isBalanced(root->left)&&isBalanced(root->right); 
+    }
+    
+    public: int height(TreeNode* root)
+{
+   if(root==NULL)
+   return 0;
+   int left=height(root->left);
+   int right=height(root->right);
+   return max(left,right)+1;
+}
+};
diff --git a/minDepthOfBinaryTree.java b/minDepthOfBinaryTree.java
@@ -0,0 +1,20 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+public class Solution {
+    public int minDepth(TreeNode root) {
+        if(root==null)
+        {
+            return 0;
+        }
+      if(root.left==null) return(minDepth(root.right)+1);
+      if(root.right==null) return (minDepth(root.left)+1);
+        return ( Math.min(minDepth(root.left),minDepth(root.right))+1);
+      }
+}
diff --git a/pathSum.java b/pathSum.java
@@ -0,0 +1,18 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+public class Solution {
+    public boolean hasPathSum(TreeNode root, int sum) {
+        if(root==null)
+        return false;
+        if(root.left==null&&root.right==null&&sum-root.val==0)
+        return true;
+        return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
+    }
+}
diff --git a/pathSum3.java b/pathSum3.java
@@ -0,0 +1,34 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+public class Solution {
+    public int pathSum(TreeNode root, int sum) {
+          if (root == null) return 0;
+        return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
+    }
+    
+    private int pathSumFrom(TreeNode node, int sum) {
+        if (node == null) return 0;
+        return (node.val == sum ? 1 : 0) 
+            + pathSumFrom(node.left, sum - node.val) + pathSumFrom(node.right, sum - node.val);
+    }
+}    
+  /*      
+       if(root==null)
+       return 0;
+  return (pathSumFrom(root,sum)+pathSumFrom(root.left,sum)+pathSumFrom(root.right,sum));
+    }
+    public int pathSumFrom(TreeNode root, int sum)
+    {
+         if (root==null)     return 0;
+         return ((root.val==sum?1:0)+pathSumFrom(root.left,sum-root.val)+pathSumFrom(root.right,sum-root.val));
+       
+    }
+*/
+
