LintCode: Max Tree

ivan_qhz 发布于2019-07-30 14:42 / 1590人阅读

摘要：题目此题和很类似，所以第一反应使用递归做。递归的解法过不了，会显示超时比递归的更好的方法是用，比较难想到，代码参考了思路是用一个单调递减栈寻找最大值。这个操作可以帮我们顺利找到左子树和父节点。

题目

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()

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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