[leetcode]Unique Binary Search Trees II @ Python

原题地址:https://oj.leetcode.com/problems/unique-binary-search-trees-ii/

题意:接上一题,这题要求返回的是所有符合条件的二叉查找树,而上一题要求的是符合条件的二叉查找树的棵数,我们上一题提过,求个数一般思路是动态规划,而枚举的话,我们就考虑dfs了。dfs(start, end)函数返回以start,start+1,...,end为根的二叉查找树。

代码:

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

class Solution:
    # @return a list of tree node
    def dfs(self, start, end):
        if start > end: return [None]
        res = []
        for rootval in range(start, end+1):        #rootval为根节点的值,从start遍历到end
            LeftTree = self.dfs(start, rootval-1)
            RightTree = self.dfs(rootval+1, end)
            for i in LeftTree:                #i遍历符合条件的左子树
                for j in RightTree:              #j遍历符合条件的右子树
                    root = TreeNode(rootval)
                    root.left = i
                    root.right = j
                    res.append(root)
        return res
    def generateTrees(self, n):
        return self.dfs(1, n)

 

[leetcode]Unique Binary Search Trees II @ Python,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。