[LintCode] Max Tree

afishhhhh 发布于2019-08-14 16:42 / 3267人阅读

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

Example

Given [2, 5, 6, 0, 3, 1], the max tree constructed by this array is:

Note

Recursion会TLE，用Stack做吧。

Solution Recursion

public class Solution {
    public TreeNode maxTree(int[] A) {
        if (A == null || A.length == 0) return null;
        return buildMax(A, 0, A.length-1);
    }
    public TreeNode buildMax(int[] A, int start, int end) {
        if (start > end) return null;
        int max = Integer.MIN_VALUE;
        int maxIndex = -1;
        for (int i = start; i <= end; i++) {
            if (A[i] >= max) {
                max = A[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(max);
        root.left = buildMax(A, start, maxIndex-1);
        root.right = buildMax(A, maxIndex+1, end);
        return root;
    }
}

Stack

public class Solution {
    public TreeNode maxTree(int[] A) {
        if (A == null || A.length == 0) return null;
        Stack stack = new Stack<>();
        for (int i = 0; i < A.length; i++) {
            //遍历A的每个元素，创造结点node
            TreeNode node = new TreeNode(A[i]);
            //将stack中小于当前结点的结点都pop出来，存为当前结点的左子树
            while (!stack.isEmpty() && node.val >= stack.peek().val) node.left = stack.pop();
            //如果stack仍非空，剩下的结点一定大于当前结点，所以将当前结点存为stack中结点的右子树；而stack中结点本来的右子树之前已经存为当前结点的左子树了
            if (!stack.isEmpty()) stack.peek().right = node;
            //stack中存放结点的顺序为：底部为完整的max tree，从下向上是下一层孩子结点的备份，顶部是当前结点的备份
            stack.push(node);
        }
        TreeNode root = stack.pop();
        while (!stack.isEmpty()) root = stack.pop();
        return root;
    }
}

海外云主机云服务器 LintCode LintCode134_LRU tree max()

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

转载请注明本文地址：https://www.ucloud.cn/yun/66254.html

LintCode: Max Tree

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

ivan_qhz 2019-07-30 14:42 评论0 收藏0
[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] 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