如何重建python二叉樹、求出禮物的最大價(jià)值以及計(jì)算1+2+…+n

如何重建python二叉樹、求出禮物的最大價(jià)值以及計(jì)算1+2+…+n，針對這個(gè)問題，這篇文章詳細(xì)介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問題的小伙伴找到更簡單易行的方法。

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。

例如，給出

前序遍歷 preorder = [3,9,20,15,7]

中序遍歷 inorder = [9,3,15,20,7]

返回如下的二叉樹：

    3

   / \

  9  20

    /  \

   15   7

限制：

0 <= 節(jié)點(diǎn)個(gè)數(shù) <= 5000

解題思路：

1，本題考察二叉樹的基礎(chǔ)：前序遍歷、中序遍歷

前序遍歷特點(diǎn)：根節(jié)點(diǎn)在第一個(gè)位置

2，找到根元素后，可以根據(jù)中序遍歷的性質(zhì)，把二叉樹分為兩個(gè)部分，因?yàn)橹蹈鞑幌嗤?，所以，中序?shù)組中和根元素相同位置左側(cè)是左子樹

3，前序遍歷和中序遍歷的相同點(diǎn)，都是先遍歷左子樹和根節(jié)點(diǎn)

4，假設(shè)左子樹長度為i，那么前序遍歷中，1到i一定屬于左子樹

5，遞歸解決

代碼實(shí)現(xiàn)

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func buildTree(preorder []int, inorder []int) *TreeNode {   if len(preorder)==0{       return nil   }
   i:=0   for i<len(inorder)&& inorder[i]!=preorder[0]{       i++   }   l:=buildTree(preorder[1:i+1],inorder[:i])   r:=buildTree(preorder[i+1:],inorder[i+1:])   return &TreeNode{       Left:l,       Val:preorder[0],       Right:r,   }}

禮物的最大價(jià)值

在一個(gè) m*n 的棋盤的每一格都放有一個(gè)禮物，每個(gè)禮物都有一定的價(jià)值（價(jià)值大于 0）。你可以從棋盤的左上角開始拿格子里的禮物，并每次向右或者向下移動(dòng)一格、直到到達(dá)棋盤的右下角。給定一個(gè)棋盤及其上面的禮物的價(jià)值，請計(jì)算你最多能拿到多少價(jià)值的禮物？

示例 1:

輸入: 

[

  [1,3,1],

  [1,5,1],

  [4,2,1]

]

輸出: 12

解釋: 路徑 1→3→5→2→1 可以拿到最多價(jià)值的禮物

提示：

0 < grid.length <= 200

0 < grid[0].length <= 200

解題思路：

1，這是一個(gè)典型的動(dòng)態(tài)規(guī)劃題目

2，狀態(tài)轉(zhuǎn)移方程 dp[i,j]=max(dp[i-1,j],dp[i,j-1])+grid[i-1,j-1]

3,為了方便計(jì)算，dp的大小比grid 兩個(gè)維度都加1

代碼實(shí)現(xiàn)：

func maxValue(grid [][]int) int {   dp:=make([][]int,len(grid)+1)   for i:=0;i<len(dp);i++{       dp[i]=make([]int,len(grid[0])+1)   }   for i:=1;i<=len(grid);i++{       for j:=1;j<=len(grid[0]);j++{          dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1]       }   }   return dp[len(grid)][len(grid[0])]   }
func max(a,b int)int{    if a>b{        return a    }    return b}

求1+2+…+n

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字及條件判斷語句（A?B:C）。

示例 1：

輸入: n = 3

輸出: 6

示例 2：

輸入: n = 9

輸出: 45

限制：

1 <= n <= 10000

解題思路：

1，這個(gè)題目沒有啥難度，就是比較賤

2，求和方式有三個(gè)：迭代、求和公式、遞歸

3，限制了前倆，就是第三個(gè)

代碼實(shí)現(xiàn)

func sumNums(n int) int {    if n==1{        return n    }    return sumNums(n-1)+n}

關(guān)于如何重建python二叉樹、求出禮物的最大價(jià)值以及計(jì)算1+2+…+n問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。