for(? x : xs) {
while(!stack.isEmpty() && stack.peek() < x) {
stack.pop()
}
stack.push(x)
}https://blog.csdn.net/qq_42265220/article/details/120563024
class Solution {
public int[] finalPrices(int[] prices) {
int len = prices.length;
int[] ans = new int[len];
ans[len-1] = prices[len-1];
Deque<Integer> deque = new ArrayDeque<>();
for (int i = len-1; i >= 0; i--) {
while (!deque.isEmpty() && deque.peek() > prices[i]) {
deque.pop();
}
ans[i] = deque.isEmpty() ? prices[i] : prices[i] - deque.peek();
deque.push(prices[i]);
}
return ans;
}
}
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int len = temperatures.length;
int[] ans = new int[len];
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < len; i++) {
int temperature = temperatures[i];
while (!deque.isEmpty() && temperature > temperatures[deque.peek()]) {
int prevIndex = deque.pop();
ans[prevIndex] = i - prevIndex;
}
deque.push(i);
}
return ans;
}
}
public int evalRPN(String[] tokens) {
Deque<Integer> deque = new ArrayDeque<>();
String expression = "+-*/";
for (int i = 0; i < tokens.length; i++) {
if (expression.contains(tokens[i])) {
int rightNum = deque.pop();
int leftNum = deque.pop();
switch (tokens[i]) {
case "+" :
deque.push(leftNum + rightNum);
break;
case "-" :
deque.push(leftNum - rightNum);
break;
case "*" :
deque.push(leftNum * rightNum);
break;
case "/" :
deque.push(leftNum / rightNum);
break;
}
} else {
deque.push(Integer.parseInt(tokens[i]));
}
}
return deque.pop();
}// Definition for a bianry tree node:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val){ this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}根结点 ---> 左子树 ---> 右子树
/**
* 递归先序遍历
* */
public void preOrderRecursion(TreeNode node){
if(node==null) //如果结点为空则返回
return;
visit(node);//访问根节点
preOrderRecursion(node.left);//访问左孩子
preOrderRecursion(node.right);//访问右孩子
}左子树---> 根结点 ---> 右子树
/**
* 递归中序遍历
* */
public void preOrderRecursion(TreeNode node){
if(node==null) //如果结点为空则返回
return;
preOrderRecursion(node.left);//访问左孩子
visit(node);//访问根节点
preOrderRecursion(node.right);//访问右孩子
}左子树 ---> 右子树 ---> 根结点
/**
* 递归后序遍历
* */
public void preOrderRecursion(TreeNode node){
if(node==null) //如果结点为空则返回
return;
preOrderRecursion(node.left);//访问左孩子
preOrderRecursion(node.right);//访问右孩子
visit(node);//访问根节点
}层次遍历的代码比较简单，只需要一个队列即可，先在队列中加入根结点。之后对于任意一个结点来说，在其出队列的时候，访问之。同时如果左孩子和右孩子有不为空的，入队列。代码如下：
public void levelTraverse(TreeNode root) {
if (root == null) {
return;
}
// 队列:先进先出FIFO
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val+" ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}其实深度遍历就是上面的前序、中序和后序。但是为了保证与广度优先遍历相照应，也写在这。代码也比较好理解，其实就是前序遍历，代码如下：
public void depthOrderTraverse(TreeNode root) {
if (root == null) {
return;
}
// 栈:后进先出LIFO
LinkedList<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.val+" ");
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
public class No104 {
int maxDepth = 0;
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
recursion(root, 1);
return maxDepth;
}
public void recursion(TreeNode node, int depth) {
if (node.left != null) {
recursion(node.left, depth + 1);
}
if (node.right != null) {
recursion(node.right, depth + 1);
}
// 到这里，说明节点node是叶子节点
maxDepth = depth > maxDepth ? depth : maxDepth;
}
}- 深度优先搜索
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
}- 广度优先搜索
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int ans = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
size--;
}
ans++;
}
return ans;
}
}将下图的二叉树从上至下、从左至右存放在一个一维数组中，对应的一维数组为[1,2,3,4,5,6,7,8,9,10]。
下标为i的元素所对应的结点的左右结点在数组中的下标为2i+1和2i+2
因此，给定一个数组，我们可以从第一个元素开始递归创建二叉树。
public TreeNode buildTree(int[] nums, int i){
if(nums.length==0)
return null;
if(i>=nums.length)
return null;
TreeNode root = new TreeNode(nums[i]);
root.left = buildTree(nums,2*i+1);
root.right = buildTree(nums,2*i+2);
return root;
}
public class No106 {
int[] postorder;
int[] inorder;
int len;
int rootIndex;
HashMap<Integer,Integer> inorderMap = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.inorder = inorder;
this.postorder = postorder;
this.len = inorder.length;
this.rootIndex = len - 1;
for (int i = 0; i < len; i++) {
inorderMap.put(inorder[i] , i);
}
return helper(0, len - 1);
}
public TreeNode helper (int inLeft, int inRight) {
if (inLeft > inRight) {
return null;
}
int rootVal = postorder[rootIndex];
// 根据 root 所在位置分成左右两棵子树
int inIndex = inorderMap.get(rootVal);
TreeNode root = new TreeNode(rootVal);
rootIndex--;
// 构造右子树
root.right = helper(inIndex + 1,inRight);
// 构造左子树
root.left = helper(inLeft , inIndex - 1);
return root;
}
}
class Test {
public static void main(String[] args) {
No106 test = new No106();
int[] inorder = {9,3,15,20,7};
int[] postorder = {9,15,7,20,3};
test.buildTree(inorder,postorder);
}
}