資訊專欄INFORMATION COLUMN
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.
Given [2, 5, 6, 0, 3, 1], the max tree constructed by this array is:
6 / 5 3 / / 2 0 1Note
Recursion會(huì)TLE，用Stack做吧。
Solution Recursionpublic 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的每個(gè)元素，創(chuàng)造結(jié)點(diǎn)node
TreeNode node = new TreeNode(A[i]);
//將stack中小于當(dāng)前結(jié)點(diǎn)的結(jié)點(diǎn)都pop出來，存為當(dāng)前結(jié)點(diǎn)的左子樹
while (!stack.isEmpty() && node.val >= stack.peek().val) node.left = stack.pop();
//如果stack仍非空，剩下的結(jié)點(diǎn)一定大于當(dāng)前結(jié)點(diǎn)，所以將當(dāng)前結(jié)點(diǎn)存為stack中結(jié)點(diǎn)的右子樹；而stack中結(jié)點(diǎn)本來的右子樹之前已經(jīng)存為當(dāng)前結(jié)點(diǎn)的左子樹了
if (!stack.isEmpty()) stack.peek().right = node;
//stack中存放結(jié)點(diǎn)的順序?yàn)椋旱撞繛橥暾膍ax tree，從下向上是下一層孩子結(jié)點(diǎn)的備份，頂部是當(dāng)前結(jié)點(diǎn)的備份
stack.push(node);
}
TreeNode root = stack.pop();
while (!stack.isEmpty()) root = stack.pop();
return root;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66254.html
摘要：題目此題和很類似，所以第一反應(yīng)使用遞歸做。遞歸的解法過不了，會(huì)顯示超時(shí)比遞歸的更好的方法是用，比較難想到，代碼參考了思路是用一個(gè)單調(diào)遞減棧尋找最大值。這個(gè)操作可以幫我們順利找到左子樹和父節(jié)點(diǎn)。 題目 Given an integer array with no duplicates. A max tree building on this array is defined as fol...
摘要：和其它題目一樣，依然是遞歸的做法。注意若樹的結(jié)點(diǎn)范圍為，那么至少有個(gè)數(shù)在左子樹上，所以語(yǔ)句里用了號(hào)。另外，最后一句是調(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...
摘要：唯一需要注意的就是的賦值取左右子樹的的較大值，最后一層的獨(dú)立結(jié)點(diǎn)的為對(duì)應(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...
摘要：題目是要查詢到這個(gè)區(qū)間內(nèi)某一點(diǎn)的。值是從最底層的子節(jié)點(diǎn)值里取最大值。因此，不用太復(fù)雜，遞歸就可以了。與所不同的是，對(duì)所給區(qū)間內(nèi)的元素個(gè)數(shù)求和，而非篩選。這樣就會(huì)出現(xiàn)的情況，視作本身處理。 Segment Tree Query Problem For an integer array (index from 0 to n-1, where n is the size of this ar...
摘要：調(diào)用函數(shù)更新路徑和的最大值，而函數(shù)本身需要遞歸，返回的是單邊路徑和。所以函數(shù)要返回的是，主函數(shù)中返回的卻是最上一層根節(jié)點(diǎn)處和的較大值，與之前遍歷過所有路徑的最大值之間的最大值。 Problem Given a binary tree, find the maximum path sum. The path may start and end at any node in the tre...
閱讀 2855·2023-04-25 17:59
閱讀 685·2023-04-25 15:05
閱讀 675·2021-11-25 09:43
閱讀 3038·2021-10-12 10:13
閱讀 3545·2021-09-27 13:59
閱讀 3589·2021-09-23 11:21
閱讀 3889·2021-09-08 09:35
閱讀 571·2019-08-29 17:12
