python中二叉搜索樹的示例分析

發(fā)布時間：2021-12-13 16:24:58 來源：億速云閱讀：133 作者：柒染欄目：大數(shù)據(jù)

本篇文章為大家展示了python中二叉搜索樹的示例分析，內(nèi)容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。

給定一個整數(shù) n，生成所有由 1 ... n 為節(jié)點所組成的二叉搜索樹。

示例:

輸入: 3
輸出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解釋:
以上的輸出對應(yīng)以下 5 種不同結(jié)構(gòu)的二叉搜索樹：

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

解題思路：

1，對于二叉樹相關(guān)的問題，都可以遞歸來解

2，對于start<i<end可以構(gòu)成的二叉搜索樹有：

A，start:i-1能夠組成的二叉樹作為左子樹

B，i＋1:end能夠組成的二叉樹作為右子樹

3，注意邊界情況，左（右）子樹為空， start＝＝end，start＋1=＝end

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func generateTrees(n int) []*TreeNode {     var t  []*TreeNode    if n<1{        return t    }    return bst(1,n)}
func bst(start,end int)[]*TreeNode{    var t  []*TreeNode    if end<start{        return t    }    if start==end{        t=append(t,&TreeNode{Val:start})        return t    }    if start+1==end{        t=append(t,&TreeNode{Val:start,Right:&TreeNode{Val:end}})        t=append(t,&TreeNode{Val:end,Left:&TreeNode{Val:start}})        return t    }    for i:=start;i<=end;i++{        left:=bst(start,i-1)        right:=bst(i+1,end)        if len(left)<=0{             for _,r:=range(right){                root:=&TreeNode{Val:i,Right:r}                t=append(t,root)            }        }else if len(right)<=0{               for _,l:=range(left){                root:=&TreeNode{Val:i,Left:l}                t=append(t,root)            }        }else{        for _,l:=range(left){            for _,r:=range(right){                root:=&TreeNode{Val:i,Left:l,Right:r}                t=append(t,root)            }        }        }    }     return t}

上述內(nèi)容就是python中二叉搜索樹的示例分析，你們學(xué)到知識或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識儲備，歡迎關(guān)注億速云行業(yè)資訊頻道。

向AI問一下細(xì)節(jié)

python中二叉搜索樹的示例分析

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽