亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

[LintCode] Max Tree

afishhhhh / 3402人閱讀

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:

    6
   / 
  5   3
 /   / 
2   0   1
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的每個元素，創(chuàng)造結(jié)點node
            TreeNode node = new TreeNode(A[i]);
            //將stack中小于當(dāng)前結(jié)點的結(jié)點都pop出來，存為當(dāng)前結(jié)點的左子樹
            while (!stack.isEmpty() && node.val >= stack.peek().val) node.left = stack.pop();
            //如果stack仍非空，剩下的結(jié)點一定大于當(dāng)前結(jié)點，所以將當(dāng)前結(jié)點存為stack中結(jié)點的右子樹；而stack中結(jié)點本來的右子樹之前已經(jīng)存為當(dāng)前結(jié)點的左子樹了
            if (!stack.isEmpty()) stack.peek().right = node;
            //stack中存放結(jié)點的順序為：底部為完整的max tree，從下向上是下一層孩子結(jié)點的備份，頂部是當(dāng)前結(jié)點的備份
            stack.push(node);
        }
        TreeNode root = stack.pop();
        while (!stack.isEmpty()) root = stack.pop();
        return root;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/66254.html

相關(guān)文章

  • LintCode: Max Tree

    摘要：題目此題和很類似，所以第一反應(yīng)使用遞歸做。遞歸的解法過不了，會顯示超時比遞歸的更好的方法是用，比較難想到，代碼參考了思路是用一個單調(diào)遞減棧尋找最大值。這個操作可以幫我們順利找到左子樹和父節(jié)點。 題目 Given an integer array with no duplicates. A max tree building on this array is defined as fol...

    ivan_qhz 評論0 收藏0

  • [LintCode] Segment Tree Modify

    摘要：和其它題目一樣，依然是遞歸的做法。注意若樹的結(jié)點范圍為，那么至少有個數(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...

    CoffeX 評論0 收藏0

  • [LintCode] Segment Tree Build & Segment Tree B

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

    honhon 評論0 收藏0

  • [LintCode] Segment Tree Query I & Segment Tree

    摘要：題目是要查詢到這個區(qū)間內(nèi)某一點的。值是從最底層的子節(jié)點值里取最大值。因此，不用太復(fù)雜，遞歸就可以了。與所不同的是，對所給區(qū)間內(nèi)的元素個數(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...

    vibiu 評論0 收藏0

  • [LintCode/LeetCode] Binary Tree Maximum Path Sum

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

    cnTomato 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<