【lc刷题 day4】栈的压入、弹出序列从上到下打印二叉树二叉搜索树的后序遍历数列

剑指offer 31.栈的压入、弹出序列 medium

class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {Stack<Integer> s=new Stack<>();int i=0;for(int j=0;j<pushed.length;j++){s.push(pushed[j]);while(!s.isEmpty()&&popped[i]==s.peek()){s.pop();i++;}}return s.isEmpty();}
}

一开始没有思路，看题解才写出来的
建一个栈，把pushed中的元素都压进去，如果与poped中对应就弹出
时间复杂度O(n),空间复杂度O(n)

剑指Offer 32-I.从上到下打印为二叉树 medium

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {List<List<Integer>> list=new ArrayList<>();public int[] levelOrder(TreeNode root) {level(0,root);int count=0;for(int i=0;i<list.size();i++){count+=list.get(i).size();}int[] res=new int[count];int k=0;for(int i=0;i<list.size();i++){for(int j=0;j<list.get(i).size();j++){res[k]=list.get(i).get(j);k++;}}return res;}void level(int depth,TreeNode node){if(node==null) return;if(list.size()<=depth){List<Integer> l=new ArrayList<>();list.add(l);}list.get(depth).add(node.val);level(depth+1,node.left);level(depth+1,node.right);}
}

重点是建立一个双层链表List<List<Integer>> list
每一层的元素存在一个链表中
时间复杂度O(n),空间复杂度O(n)

剑指Offer 32-II.从上打下打印二叉树 easy

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {List<List<Integer>> list=new ArrayList<>();public List<List<Integer>> levelOrder(TreeNode root) {level(0,root);return list;}void level(int depth,TreeNode node){if(node==null) return;if(depth==list.size()){List<Integer> l=new ArrayList<>();list.add(l);}list.get(depth).add(node.val);depth++;level(depth,node.left);level(depth,node.right);}
}

跟上面那道题用的一个方法

剑指Offer 32-III.从上到下打印二叉树 medium

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {List<List<Integer>> list=new ArrayList<>();public List<List<Integer>> levelOrder(TreeNode root) {level(0,root);return list;}void level(int depth,TreeNode node){if(node==null) return;if(depth==list.size()){List<Integer> l=new ArrayList<>();list.add(l);}if(depth%2==0){list.get(depth).add(node.val);}else{list.get(depth).add(0,node.val);}level(depth+1,node.left);level(depth+1,node.right);}
}

跟上面一道题一样
List<Integer> 的一个方法重载 list.add(i,n)即在第i个元素插入n，list.add(n）是默认插到尾部，如果想插在头部，则是list.add(0,n)

剑指Offer 33.二叉搜索树的后序遍历数列 medium

class Solution {public boolean verifyPostorder(int[] postorder) {return recur(postorder,0,postorder.length-1);}boolean recur(int[] postorder,int i,int j){if(i>=j) return true;int m=i;while(postorder[m]<postorder[j]){m++;}int n=m;while(postorder[n]>postorder[j]){n++;}return n==j&&recur(postorder,i,m-1)&&recur(postorder,m,j-1);}
}