[Function add]

Seanforfun · Seanforfun · commit f698861e87f8 · 2019-04-08T16:23:46.000-04:00
1. Add leetcode solutions with tag tree.
diff --git a/leetcode/124. Binary Tree Maximum Path Sum.md b/leetcode/124. Binary Tree Maximum Path Sum.md
@@ -58,4 +58,32 @@ class Solution {
         return Math.max(cur, Math.max(cur + leftSum, cur + rightSum)); //返回到上一层的可能性有三种， 只返回当前结点，左结点往上， 右结点往上。
     }
 }
-```
+```
+
+### Second Time
+* Method 1: Recursion
+	```Java
+	/**
+	 * Definition for a binary tree node.
+	 * public class TreeNode {
+	 *     int val;
+	 *     TreeNode left;
+	 *     TreeNode right;
+	 *     TreeNode(int x) { val = x; }
+	 * }
+	 */
+	class Solution {
+		private int max = Integer.MIN_VALUE;
+		public int maxPathSum(TreeNode root) {
+			return Math.max(max(root), this.max);
+		}
+		private int max(TreeNode node){
+			if(node == null) return 0;
+			int left = Math.max(max(node.left), 0);
+			int right = Math.max(max(node.right), 0);
+			int res = Math.max(node.val, node.val + left + right);
+			this.max = Math.max(max, res);
+			return Math.max(node.val, Math.max(node.val + left, node.val + right));
+		}
+	}
+	```
diff --git a/leetcode/129. Sum Root to Leaf Numbers.md b/leetcode/129. Sum Root to Leaf Numbers.md
@@ -106,4 +106,39 @@ class Solution {
         }
     }
 }
-```
+```
+
+### Third Time
+* Method 1: dfs
+	```Java
+	/**
+	 * Definition for a binary tree node.
+	 * public class TreeNode {
+	 *     int val;
+	 *     TreeNode left;
+	 *     TreeNode right;
+	 *     TreeNode(int x) { val = x; }
+	 * }
+	 */
+	class Solution {
+		private List<Integer> path;
+		public int sumNumbers(TreeNode root) {
+			this.path = new ArrayList<>();
+			dfs(root, 0);
+			int res = 0;
+			for(Integer n : path)
+				res += n;
+			return res;
+		}
+		private void dfs(TreeNode node, int cur){
+			if(node == null){
+				this.path.add(cur);
+				return;
+			}
+			cur = cur * 10 + node.val;
+			if(node.left == null && node.right == null) dfs(null, cur);
+			if(node.left != null) dfs(node.left, cur);
+			if(node.right != null) dfs(node.right, cur);
+		}
+	}
+	```
diff --git a/leetcode/257. Binary Tree Paths.md b/leetcode/257. Binary Tree Paths.md
@@ -102,3 +102,34 @@ class Solution {
     }
 }
 ```
+
+### Third Time
+* Method 1: dfs
+	```Java
+	/**
+	 * Definition for a binary tree node.
+	 * public class TreeNode {
+	 *     int val;
+	 *     TreeNode left;
+	 *     TreeNode right;
+	 *     TreeNode(int x) { val = x; }
+	 * }
+	 */
+	class Solution {
+		private List<String> result;
+		public List<String> binaryTreePaths(TreeNode root) {
+			this.result = new ArrayList<>();
+			if(root == null) return result;
+			if(root.left == null && root.right == null) result.add(root.val + "");
+			if(root.left != null) dfs(root.left, root.val + "");
+			if(root.right != null) dfs(root.right, root.val + "");
+			return result;
+		}
+		private void dfs(TreeNode node, String s){
+			String cur = s + "->" + node.val;
+			if(node.left == null && node.right == null) result.add(cur);
+			if(node.left != null) dfs(node.left, cur);
+			if(node.right != null) dfs(node.right, cur);
+		}
+	}
+	```
diff --git a/leetcode/543. Diameter of Binary Tree.md b/leetcode/543. Diameter of Binary Tree.md
@@ -0,0 +1,49 @@
+## 543. Diameter of Binary Tree
+
+### Question:
+ Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
+ 
+```
+Example:
+Given a binary tree
+
+          1
+         / \
+        2   3
+       / \     
+      4   5    
+
+Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
+```
+
+Note: The length of path between two nodes is represented by the number of edges between them. 
+
+### Solution:
+* Method 1: Divide and conquer(Recursion).
+    ```Java
+    /**
+     * Definition for a binary tree node.
+     * public class TreeNode {
+     *     int val;
+     *     TreeNode left;
+     *     TreeNode right;
+     *     TreeNode(int x) { val = x; }
+     * }
+     */
+    class Solution {
+        private int result;
+        public int diameterOfBinaryTree(TreeNode root) {
+            if(root == null) return 0;
+            maxPath(root);
+            return this.result - 1;
+        }
+        private int maxPath(TreeNode root){
+            if(root == null) return 0;
+            int left = maxPath(root.left);
+            int right = maxPath(root.right);
+            this.result = Math.max(result, left + right + 1);
+            return Math.max(left, right) + 1;
+        }
+    }
+    ```
+   
diff --git a/leetcode/687. Longest Univalue Path.md b/leetcode/687. Longest Univalue Path.md
@@ -0,0 +1,71 @@
+## 687. Longest Univalue Path
+
+### Question:
+ Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.
+
+Note: The length of path between two nodes is represented by the number of edges between them.
+
+```
+Example 1:
+
+Input:
+
+              5
+             / \
+            4   5
+           / \   \
+          1   1   5
+
+Output:
+
+2
+
+Example 2:
+
+Input:
+
+              1
+             / \
+            4   5
+           / \   \
+          4   4   5
+
+Output:
+
+2
+```
+
+Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000. 
+
+### Solution:
+* Method 1: Divide and conquer(Recursion).
+    ```Java
+    /**
+     * Definition for a binary tree node.
+     * public class TreeNode {
+     *     int val;
+     *     TreeNode left;
+     *     TreeNode right;
+     *     TreeNode(int x) { val = x; }
+     * }
+     */
+    class Solution {
+        private int result;
+        public int longestUnivaluePath(TreeNode root) {
+            if(root == null) return 0;
+            getPath(root);
+            return this.result - 1;
+        }
+        private int getPath(TreeNode node){
+            if(node == null) return 0;
+            int left = getPath(node.left);
+            int right = getPath(node.right);
+            int res = 1 + ((node.left == null || node.left.val == node.val) ? left: 0)
+                + ((node.right == null || node.right.val == node.val) ? right: 0);
+            this.result = Math.max(result, res);
+            return Math.max((node.left == null || node.left.val == node.val) ? left: 0, 
+                           (node.right == null || node.right.val == node.val) ? right: 0) + 1;
+        }
+    }
+    ```
+   
