leetcode-95-Unique Binary Search Trees II

Tony_Zby 發布于2019-07-31 11:11 / 1496人閱讀

摘要：題目解讀窮舉列出所有二叉樹的結構類型。重點動態規劃，關注臨近，，之間的關系應用窮舉組合，動態規劃窮舉組合，適用于相鄰元素有規律。處注意邊界值的情況。不能有重復，遺漏。

題目解讀： 窮舉列出所有二叉樹的結構類型。
重點： 動態規劃，關注臨近root，left，right之間的關系
應用：窮舉組合，動態規劃窮舉組合，適用于相鄰元素有規律。
bug處：注意邊界值的情況。不能有重復，遺漏。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def generateTrees(self, n):
        def dfs(left,right):
            nodes=list()
            for root in range(left,right+1):
                print("root=>",root)
                # node=TreeNode(root)
                for node_left in dfs(left,root-1):
                    # node_left=TreeNode(val_left)
                    for node_right in dfs(root+1,right):
                        node_root=TreeNode(root)
                        node_root.left=node_left
                        # node_right=TreeNode(val_right)
                        node_root.right=node_right
                        # nodes.append(node_root)
                        nodes.append(node_root)
            return nodes or [None,]
        if n<1:
            return []
        return dfs(1,n)

if __name__=="__main__":
    n=0
    st=Solution()
    out=st.generateTrees(n)
    # out_vals=[(elem.left.val if hasattr(elem.left,"val") else None,elem.right.val if hasattr(elem.right,"val") else None) for elem in out]
    print(out)
    print(len(out))

云服務器 GPU云服務器 binary-search binary-search-tree Trees Binary

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/44761.html

leetcode95-96 Unique Binary Search Trees I-II

摘要：在這里我們使用數組中下標為的位置來記錄個元素可以組成的平衡二叉樹的數量。在遞歸的過程中，我們找到以當前節點作為根節點的所有平衡二叉樹，并將結果以形式返回上一級調用。題目要求 Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example, Gi...

morgan 2019-08-15 11:06 評論0 收藏0
[Leetcode] Unique Binary Search Trees 唯一二叉搜索樹

摘要：而根可以選擇從到的任意的數，唯一二叉樹的總數，就是根為到的樹相加。所以該問題化簡為以為根，其唯一左子樹和右子樹各有多少，這就是個動態規劃的問題了。 Unique Binary Search Trees I && II 解法請見：https://yanjia.li/zh/2019/02/... Given n, how many structurally unique BSTs (b...

enrecul101 2019-08-14 12:38 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
[LeetCode] 96. Unique Binary Search Trees I &

Unique Binary Search Trees Problem Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? Example Given n = 3, there are a total of 5 unique BSTs. 1 3 3...

nidaye 2019-08-14 15:22 評論0 收藏0
272. Closest Binary Search Tree Value II

摘要：題目鏈接的值大小順序實際上就是滿足的條件，所以直接中序遍歷，過程中維護一個，放入個當前離最近的值，的時，新的值和的距離如果小于隊首的那個值和的距離那么移除隊首，如果，且新的距離大于等于隊首的距離，直接退出，返回隊列中的所有結果。 272. Closest Binary Search Tree Value II 題目鏈接：https://leetcode.com/problems... ...

NusterCache 2019-08-14 17:35 評論0 收藏0