程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode Unique Binary Search Trees II

LeetCode Unique Binary Search Trees II

編輯:關於C++

LeetCode解題之Unique Binary Search Trees II


原題

給定1到n這n個數,用它們能夠構成多少種形狀不同的二叉搜索樹。將所有的二叉搜索樹羅列出來。

注意點:

這n個數都要是二叉搜索樹的節點,不能只取部分

例子:

輸入: n = 3

輸出:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

解題思路

Unique Binary Search Trees 只要求不同二叉搜索樹的數目,現在要求把所有的樹的結構都打印出來。所以在遞歸的時候要把樹拼裝出來,而不是僅僅計算數目。而且同一個子樹可能會在不同的二叉搜索樹中多次出現,為了不重復計算,就用一個map來緩存構造過的樹形結構。

AC源碼

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n == 0:
            return []
        self.cache = {}
        return self._generateTrees(1, n)

    def _generateTrees(self, start, end):
        if (start, end) not in self.cache:
            roots = []
            for root in range(start, end + 1):
                for left in self._generateTrees(start, root - 1):
                    for right in self._generateTrees(root + 1, end):
                        node = TreeNode(root)
                        node.left = left
                        node.right = right
                        roots.append(node)
            self.cache[(start, end)] = roots
        return self.cache[(start, end)] or [None]


if __name__ == "__main__":
    None
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved