[LintCode] Max Tree

afishhhhh 發布于2019-08-14 16:42 / 3344人閱讀

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;
    }
}

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

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/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