資訊專欄INFORMATION COLUMN
摘要：題目此題和很類似，所以第一反應(yīng)使用遞歸做。遞歸的解法過不了，會顯示超時(shí)比遞歸的更好的方法是用，比較難想到，代碼參考了思路是用一個(gè)單調(diào)遞減棧尋找最大值。這個(gè)操作可以幫我們順利找到左子樹和父節(jié)點(diǎn)。
題目
Given an integer array with no duplicates. A max tree building on this array is defined as follow:
The root is the maximum number in the array
The left subtree and right subtree are the max trees of the subarray divided by the root number.
Construct the max tree by the given array.
此題和Construct Binary Tree from Preorder and Inorder Traversal 很類似， 所以第一反應(yīng)使用遞歸做。遞歸的解法過不了lintcode，會顯示超時(shí)：
class Solution:
"""
@param: A: Given an integer array with no duplicates.
@return: The root of max tree.
"""
def maxTree(self, A):
def helper(A, start, end):
if start > end:
return None
elif start == end:
return TreeNode(A[start])
maxVal = 0
maxIndex = -1
for i in range(start, end+1):
if A[i] > maxVal:
maxVal, maxIndex = A[i], i
root = TreeNode(maxVal)
root.left = helper(A, start, maxIndex - 1)
root.right = helper(A, maxIndex + 1, end)
return root
if A is None or len(A) == 0:
return None
return helper(A, 0, len(A)-1)
比遞歸的更好的方法是用stack，比較難想到，代碼參考了：https://lefttree.gitbooks.io/...
思路是用一個(gè)單調(diào)遞減棧尋找最大值。每遍歷到一個(gè)新的數(shù)字A[i]，我們就把比這個(gè)數(shù)字小的都彈棧，直到剩下比此數(shù)字大的數(shù)字。這個(gè)操作可以幫我們順利找到左子樹和父節(jié)點(diǎn)。這個(gè)解法讓我想到了經(jīng)典的樹的非遞歸遍歷，需要再復(fù)習(xí)一下。
class Solution:
"""
@param: A: Given an integer array with no duplicates.
@return: The root of max tree.
"""
def maxTree(self, A):
stack = []
for val in A:
node = TreeNode(val)
while len(stack) > 0 and val > stack[-1].val:
node.left = stack.pop()
if len(stack) > 0:
stack[-1].right = node
stack.append(node)
return stack[0]
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/40865.html
摘要：和其它題目一樣，依然是遞歸的做法。注意若樹的結(jié)點(diǎn)范圍為，那么至少有個(gè)數(shù)在左子樹上，所以語句里用了號。另外，最后一句是調(diào)用遞歸之后的結(jié)果，必須寫在最后面。 Problem For a Maximum Segment Tree, which each node has an extra value max to store the maximum value in this nodes i...
摘要：唯一需要注意的就是的賦值取左右子樹的的較大值，最后一層的獨(dú)立結(jié)點(diǎn)的為對應(yīng)數(shù)組中的值。 Segment Tree Build I Problem The structure of Segment Tree is a binary tree which each node has two attributes start and end denote an segment / interv...
Problem Given an integer array with no duplicates. A max tree building on this array is defined as follow: The root is the maximum number in the arrayThe left subtree and right subtree are the max tre...
摘要：題目是要查詢到這個(gè)區(qū)間內(nèi)某一點(diǎn)的。值是從最底層的子節(jié)點(diǎn)值里取最大值。因此，不用太復(fù)雜，遞歸就可以了。與所不同的是，對所給區(qū)間內(nèi)的元素個(gè)數(shù)求和，而非篩選。這樣就會出現(xiàn)的情況，視作本身處理。 Segment Tree Query Problem For an integer array (index from 0 to n-1, where n is the size of this ar...
摘要：調(diào)用函數(shù)更新路徑和的最大值，而函數(shù)本身需要遞歸，返回的是單邊路徑和。所以函數(shù)要返回的是，主函數(shù)中返回的卻是最上一層根節(jié)點(diǎn)處和的較大值，與之前遍歷過所有路徑的最大值之間的最大值。 Problem Given a binary tree, find the maximum path sum. The path may start and end at any node in the tre...
閱讀 891·2023-04-26 03:04
閱讀 2935·2021-11-15 18:10
閱讀 1268·2021-09-03 10:28
閱讀 1187·2019-08-30 15:53
閱讀 966·2019-08-30 12:45
閱讀 2019·2019-08-30 11:03
閱讀 2931·2019-08-29 14:01
閱讀 2987·2019-08-28 18:24
