21、栈的压入、弹出序列

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

解法

使用一个辅助栈模拟入栈，将每个元素依次入栈，入栈后判断栈顶元素是否和输出数组对应，相对应则栈pop

依次操作输入数组的数，最后栈为空表示是符合条件的

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

21、从上往下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印

解法

这就像是广度优先搜索，使用一个队列。首先将根节点入队，判断队列是否为null作为循环条件，取出队列头元素，判断根节点是否有左子节点，有则入队；判断根节点是否有右子节点，有则入队；保存根节点的值，直到队列为null

此处使用一个ArrayList来表示队列

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<>();
   ArrayList<TreeNode> queue = new ArrayList<>(); // 用一个ArrayList模拟队列
   if (root == null) {
       return list;
   }
   queue.add(root);
   while (queue.size() != 0) {
       TreeNode temp = queue.remove(0);
       if (temp.left != null){
           queue.add(temp.left);
       }
       if (temp.right != null) {
           queue.add(temp.right);
       }
       list.add(temp.val);
   }
   return list;
}
}

22、二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果
如果是则返回true,否则返回false。
假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）

解法

根据二叉排序树的性质：根节点大于左子树，小于右子树。后序遍历找到根节点（根据后序遍历性质最后一个节点为根节点），与根节点值进行判断，从前往后进行遍历，找到左子树与右子树分割点（第一个大于根节点节点值的节点）。假如右子树有小于根节点的节点，则表示不是后续遍历…

public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
   if (sequence == null || sequence.length == 0){
       return false;
   }
   return isBST(sequence, 0, sequence.length - 1);
}
private boolean isBST(int[] seq, int start, int end){
   if (start >= end){
       return true;
   }
   int val = seq[end];
   int split = start;
   // 找到左子树，右子树分割的点，指向右子树的某一节点
   for (; split < end && seq[split] < val; split++);
   // 假如右子树节点值比根节点小，则不是后序遍历结果
   for (int i = split; i < end; i++){
       if (seq[i] < val){
           return false;
       }
   }
   // 递归判断左右子树
   return isBST(seq, start, split - 1) && isBST(seq, split, end - 1);
}
}

22、二叉树中和为某一值的路径

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。
路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

解法

这….

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 {
private ArrayList<ArrayList<Integer>> result = new ArrayList<>();
private ArrayList<Integer> list = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
   if (root == null){
       return result;
   }
   list.add(root.val);
   target = target - root.val;
   if (target == 0 && root.left == null && root.right == null){
       result.add(new ArrayList<Integer>(list));
   }
   // 分别对左右子树判断
   ArrayList<ArrayList<Integer>> result1 = FindPath(root.left, target);
   ArrayList<ArrayList<Integer>> result2 = FindPath(root.right, target);
   // 回溯到当前节点的父节点了，父节点要走另一条路径，所以要把list的当前节点值删了，给当前节点的兄弟节点腾位置
   list.remove(list.size() - 1);
   return result;
}
}

算法

21-30题

21、栈的压入、弹出序列

21、从上往下打印二叉树

22、二叉搜索树的后序遍历序列

22、二叉树中和为某一值的路径