LintCode: Max Tree

ivan_qhz 發布于2019-07-30 14:42 / 1591人閱讀

摘要：題目此題和很類似，所以第一反應使用遞歸做。遞歸的解法過不了，會顯示超時比遞歸的更好的方法是用，比較難想到，代碼參考了思路是用一個單調遞減棧尋找最大值。這個操作可以幫我們順利找到左子樹和父節點。

題目

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 很類似，所以第一反應使用遞歸做。遞歸的解法過不了lintcode，會顯示超時：

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/...

思路是用一個單調遞減棧尋找最大值。每遍歷到一個新的數字A[i]，我們就把比這個數字小的都彈棧，直到剩下比此數字大的數字。這個操作可以幫我們順利找到左子樹和父節點。這個解法讓我想到了經典的樹的非遞歸遍歷，需要再復習一下。

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]

云服務器 GPU云服務器 LintCode LintCode134_LRU tree max()

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

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

[LintCode] Segment Tree Modify

摘要：和其它題目一樣，依然是遞歸的做法。注意若樹的結點范圍為，那么至少有個數在左子樹上，所以語句里用了號。另外，最后一句是調用遞歸之后的結果，必須寫在最后面。 Problem For a Maximum Segment Tree, which each node has an extra value max to store the maximum value in this nodes i...

CoffeX 2019-08-14 16:23 評論0 收藏0
[LintCode] Segment Tree Build & Segment Tree B

摘要：唯一需要注意的就是的賦值取左右子樹的的較大值，最后一層的獨立結點的為對應數組中的值。 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...

honhon 2019-08-14 15:14 評論0 收藏0
[LintCode] Max Tree

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...

afishhhhh 2019-08-14 16:42 評論0 收藏0
[LintCode] Segment Tree Query I & Segment Tree

摘要：題目是要查詢到這個區間內某一點的。值是從最底層的子節點值里取最大值。因此，不用太復雜，遞歸就可以了。與所不同的是，對所給區間內的元素個數求和，而非篩選。這樣就會出現的情況，視作本身處理。 Segment Tree Query Problem For an integer array (index from 0 to n-1, where n is the size of this ar...

vibiu 2019-08-14 16:22 評論0 收藏0
[LintCode/LeetCode] Binary Tree Maximum Path Sum

摘要：調用函數更新路徑和的最大值，而函數本身需要遞歸，返回的是單邊路徑和。所以函數要返回的是，主函數中返回的卻是最上一層根節點處和的較大值，與之前遍歷過所有路徑的最大值之間的最大值。 Problem Given a binary tree, find the maximum path sum. The path may start and end at any node in the tre...

cnTomato 2019-08-14 15:34 評論0 收藏0