17、
public class HasSubtree_17 {
/**
* 树的子结构
* 题目描述
* 输入两棵二叉树A，B，判断B是不是A的子结构。
* （ps：我们约定空树不是任意一个树的子结构）
*
* 思路：
* 没什么更好的方法，目前就是遍历二叉树，找到相同的node ，
*
* 模式树指针和当前指针一起往下走，judge值是否相同。
*/
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root2 == null) return false;
if (root1 == null) return root2 == null? true:false;
Stack<TreeNode> stack = new Stack<>();
stack.push(root1);
while (!stack.isEmpty()){
TreeNode temp = stack.pop();
//do sth
if (temp.val == root2.val && judge(temp, root2)) return true;
if (temp.right != null) stack.push(temp.right);
if (temp.left != null) stack.push(temp.left);
}
return false;
}
public boolean judge(TreeNode root1, TreeNode root2){
if (root1 == null) return root2 == null? true:false;
if (root2 == null) return true; //主树可以不遍历到null
if (root1.val != root2.val) return false;
return judge(root1.left, root2.left) && judge(root1.right, root2.right);
}
}
18、
public class MirrorBinaryTree_18 {
/**
* 题目描述
* 操作给定的二叉树，将其变换为源二叉树的镜像。
*
* 思路：
* 这题很简单递归翻转左右节点
*/
public void Mirror(TreeNode root) {
if (root == null) return;
Mirror(root.left);
Mirror(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
}
19、
public class PrintMatrix_19 {
/**
*
*顺序打印矩阵
*题目描述
*输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，
* 例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
* 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
*
* 思路：
* 锁定左上、右下两个角标，按层打印矩阵。注意特殊情况，如同行同列。
*/
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> res = new ArrayList<>();
process(matrix,0,0,matrix.length-1,matrix[0].length-1,res);
return res;
}
public void process(int[][] matrix, int li, int lj, int ri, int rj, ArrayList<Integer> res){
if (li > ri || lj > rj) return;
if (li == ri) while (lj <= rj) res.add(matrix[li][lj++]);
if (lj == rj) while (li <= ri) res.add(matrix[li++][lj]);
int i;int j;
for (i = li,j = lj; j < rj; j++) { res.add(matrix[i][j]); }
for (i = li,j = rj; i < ri; i++) { res.add(matrix[i][j]); }
for (i = ri,j = rj; j > lj; j--) { res.add(matrix[i][j]); }
for (i = ri,j = lj; i > li; i--) { res.add(matrix[i][j]); }
process(matrix,++li,++lj,--ri,--rj,res);
}
}
20、
public class MinStack_20 {
/**
* 最小值栈
* 题目描述
* 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
* 注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。
*
* 思路:
* 这个问题核心在于最小值出栈后，如何找到之前的最小值，所以min数据结构一定是集合。
* 由于时间复杂度的限制是不可以遍历集合，所以考虑用stack。
*/
private Stack<Integer> data = new Stack<>();
private Stack<Integer> min = new Stack<>();
public void push(int node) {
if (min.isEmpty() || node <= min.peek()) min.push(node);
data.push(node);
}
public void pop() {
if (data.pop() == min.peek()) min.pop();
}
public int top() {
return data.peek();
}
public int min() {
return min.peek();
}
}
21、
public class IsPopOrder_21 {
/**
* 栈的压入弹出
*
* 题目描述
* 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
* 假设压入栈的所有数字均不相等。
* 例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，
* 但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
*
* 思路：
* 用stack模拟出入栈过程。每push一个值之前，都检验栈顶元素是否该出栈。（等于pop[j]）
* 该出则出，直到所有元素都入栈。
*
* 检验出栈是否pop[]是否出完 ， stack pop同时移动。pop空，stack空，即为true。
*/
public boolean IsPopOrder(int [] pushA,int [] popA) {
if (pushA.length != popA.length) return false;
Stack<Integer> stack = new Stack<>();
int i = 0;
int j = 0;
while (i < popA.length) {
if (stack.isEmpty() || stack.peek() != popA[j]){
stack.push(pushA[i++]);
}else {
j++;
stack.pop();
}
}
while (j < popA.length && popA[j] == stack.peek()){
j++;
stack.pop();
}
return stack.isEmpty()? true:false;
}
}
22、
public class PrintFromTopToBottom_22 {
/**
* 从上往下打印二叉树
* 题目描述
* 从上往下打印出二叉树的每个节点，同层节点从左至右打印。
*
* 思路：
* 二叉树的层序遍历，可以解决很多二叉树问题的基石。
* 核心就是 使用 队列queue。
*/
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
TreeNode ele = queue.poll();
res.add(ele.val);
if (ele.left != null) queue.add(ele.left);
if (ele.right != null) queue.add(ele.right);
}
return res;
}
}
网友评论