A 17-Line 2-D Tabular DP Solution with Explanations


  • 0
    L
    // DP[i,j] means all the possible sub trees contrstructed by nodes from i to j. 
    // DP[1,1], DP[2,2] ... are List<TreeNode> with a single node, and they
    // are initiated at beginning.
    // DP[i,0] and DP[i, i-1] are List<TreeNode> with a Null node
    // which are prepared for connecting null left/right nodes
    // Loop from left-up to right-bottom each line per loop cycle, until (1, n)
    //    0  1  2  3  4  5  6  7 (n)
    // 0 [ ][ ][ ][ ][ ][ ][ ][ ][ ]
    // 1 [X][1][ ][ ][ ][ ][ ][ ][ ]
    // 2 [X][X][2][ ][ ][ ][ ][ ][ ]
    // 3 [X][ ][X][3][ ][ ][ ][ ][ ]
    // 4 [X][ ][ ][X][4][ ][ ][ ][ ]
    // 5 [X][ ][ ][ ][X][5][ ][ ][ ]
    // 6 [X][ ][ ][ ][ ][X][6][ ][ ]
    // 7 [X][ ][ ][ ][ ][ ][X][7][ ]
    //(n)[X][ ][ ][ ][ ][ ][ ][X][n]
    //n+1[X][ ][ ][ ][ ][ ][ ][ ][X]
    
    public IList<TreeNode> GenerateTrees(int n) {
        List<TreeNode>[,] DP = new List<TreeNode>[n + 2, n + 1];
        for (int i = 1; i <= n + 1; i++)
            for(int j = 0; j <= n; j++){
                DP[i, j] = new List<TreeNode>();
                if(i == j) DP[i, j].Add(new TreeNode(i));
                else if (j == 0 || j == i - 1) DP[i, j].Add(null);
            }
        for (int cycle = n - 1; cycle >= 1; cycle--)
            for (int i = 1, j = n - cycle + 1; i <= cycle; i++, j++)
                for (int k = i; k <= j; k++)
                    foreach (var leftNode in DP[i, k - 1])
                        foreach (var rightNode in DP[k + 1, j]){
                            DP[i, j].Add(new TreeNode(k));
                            DP[i, j][DP[i, j].Count - 1].left = leftNode;
                            DP[i, j][DP[i, j].Count - 1].right = rightNode;
                        }
        return DP[1, n];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.