tree-2

znn0301 · znn0301 · commit 1412efa004e7 · 2020-10-30T20:00:32.000+08:00
diff --git a/src/main/java/com/chen/algorithm/znn/tree/test111/Solution.java b/src/main/java/com/chen/algorithm/znn/tree/test111/Solution.java
@@ -15,7 +15,7 @@ public class Solution {
 
     /**
      * 1-深度优先搜索（DFS），即递归
-     *
+     * 叶子结点都为空，需要走到叶子结点，当一个结点为空一个结点不为空时，说明叶子结点在不为空的那个节点，返回不为空
      * @param root
      * @return
      */
@@ -35,9 +35,15 @@ public int minDepth1(TreeNode root) {
             return 0;
         }
 
+        //if(root.left == null && root.right == null){
+        //    return 1;
+        //}
+
         int leftDepth = minDepth1(root.left);
         int rightDepth = minDepth1(root.right);
 
+        // 叶子结点，是左右子节点都为空的节点，当某一个子节点为空时，则返回另一个结点的高度。
+        // 当一个结点为空一个结点不为空时，说明**叶子结点**在不为空的那个节点。
         return root.left == null || root.right == null ? leftDepth + rightDepth + 1 : Math.min(leftDepth, rightDepth) + 1;
     }
 
diff --git a/src/main/java/com/chen/algorithm/znn/tree/test96/Solution.java b/src/main/java/com/chen/algorithm/znn/tree/test96/Solution.java
@@ -1,10 +1,37 @@
 package com.chen.algorithm.znn.tree.test96;
 
+import org.junit.Test;
+
 /**
  * @Auther: zhunn
  * @Date: 2020/10/29 17:49
- * @Description: 不同的二叉搜索树：动态规划
+ * @Description: 不同的二叉搜索树：1-动态规划
  */
 public class Solution {
 
+    /**
+     * 1-动态规划 求G(n)
+     * G(0) = 1，G(1) = 1
+     * G(n) = G(i-1)*G(n-i) 求和（1<= i <=n）
+     *
+     * @param n
+     * @return
+     */
+    public int numTrees(int n) {
+        int[] dp = new int[n + 1];
+        dp[0] = 1;
+        dp[1] = 1;
+
+        for (int i = 2; i <= n; i++) {
+            for (int j = 1; j <= i; j++) {
+                dp[i] += dp[j - 1] * dp[i - j];
+            }
+        }
+        return dp[n];
+    }
+
+    @Test
+    public void test() {
+        System.out.println(numTrees(3));
+    }
 }
