2018-09-30

想要种一棵树，最好的时间是十年前，其次就是现在。

---

• 树的子结构，输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
    this.val = val;

}

}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    boolean result = false;
    if(root1!=null&&root2!=null){
        if(root1.val == root2.val){result = DoseHasSubtree(root1,root2);}
        if(!result){result = DoseHasSubtree(root1.right,root2);}
        if(!result){result = DoseHasSubtree(root1.left,root2);}
    }
    return result;
}
public boolean DoseHasSubtree(TreeNode root1,TreeNode root2) {
    if(root1==null&&root2!=null)return false;
    if(root2==null)return true;
    if(root1.val!=root2.val)return false;
    return DoseHasSubtree(root1.left,root2.left)&&DoseHasSubtree(root1.right,root2.right);
}
}

---

• 二叉树的镜像

/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
    this.val = val;

}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
    TreeNode temp = null;
    if(root!=null){
        temp = root.left;
        root.left = root.right;
        root.right = temp;
        if(root.left!=null)
            Mirror(root.left);
        if(root.right!=null)
            Mirror(root.right);
    }
}
}

---

• 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.

//难缠的一题，细心一点，耐心一点
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    if(matrix.length==0)return result;
    //行数
    int n = matrix.length;
    //列数
    int m = matrix[0].length;
    if(m==0)return result;
    int layers = (Math.min(n,m)-1)/2+1;
    for(int i=0;i<layers;i++){
        //上面一行
        for(int x=i;x<m-i;x++)result.add(matrix[i][x]);
        for(int x=i+1;x<n-i;x++)result.add(matrix[x][m-1-i]);
        for(int x=m-i-2;(x>=i)&&(i!=n-i-1);x--)result.add(matrix[n-1-i][x]);
        for(int x=n-i-2;(x>i)&&(i!=m-i-1);x--)result.add(matrix[x][i]);
    }
    return result;
}
}

---

• 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
    Stack<Integer> stack = new Stack<Integer>();
    int len = pushA.length;
    if(len==0)return false;
    int popindex = 0;
    for(int i=0;i<len;i++){
        stack.push(pushA[i]);
        while(!stack.isEmpty()&&stack.peek()==popA[popindex]){
            popindex++;
            stack.pop();
        }
    }
    if(stack.isEmpty())return true;
    else return false;
}
}

---

• 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

import java.util.Stack;

public class Solution {

Stack<Integer> dataStack = new Stack<Integer>();
Stack<Integer> minStack = new Stack<Integer>();

public void push(int node) {
    dataStack.push(node);
    if(minStack.isEmpty()||node<minStack.peek())
        minStack.push(node);
    else 
        minStack.push(minStack.peek());
}

public void pop() {
    dataStack.pop();
    minStack.pop();
}

public int top() {
    return dataStack.peek();
}

public int min() {
    return minStack.peek();
}
}

---

• 从上至下层级打印二叉树

import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
    this.val = val;

}

}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    ArrayList<TreeNode> quene = new ArrayList<TreeNode>();
    quene.add(root);
    if(root==null)return list;
    while(!quene.isEmpty()){
        TreeNode node = quene.remove(0);
        if(node.left!=null)quene.add(node.left);
        if(node.right!=null)quene.add(node.right);
        list.add(node.val);
    }
    return list;
}
}

---

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
    int len = sequence.length;
    if(len==0)return false;
    if(len==1)return true;
    return Judge(sequence,0,len-1);
}
public boolean Judge(int[] a,int start,int end){
    if(start>=end)return true;
    int i = start;
    while(a[i]<a[end])
        i=i+1;//此处写++i可行，i++不可行，求解释= =
    for(int j = i;j<end;j++){
        if(a[j]<a[end])return false;
    }
    return Judge(a,start,i-1)&&Judge(a,i,end-1);
}
}