1.从上往下打印二叉树

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

import java.util.ArrayList;
import java.util.ArrayDeque;
/**
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> l = new ArrayList<Integer>();
        if (root == null) {
            return l;
        }
        
        ArrayDeque<TreeNode> q = new ArrayDeque<TreeNode>();
        q.addLast(root);
        while (q.size() > 0) {
            TreeNode t = q.peekFirst();
            l.add(q.pollFirst().val);
            if (t.left != null) {
                q.addLast(t.left);
            }
            if (t.right != null) {
                q.addLast(t.right);
            }
        }
        return l;
    }
}

没有考虑代码的健壮性，即输入为空等等情况。

2.二叉搜索树的后序遍历

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

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        // 4 7 6 13 24 9 8
        int len = 0;
        if (sequence == null || (len = sequence.length) == 0) {
            return false;
        }
        int i = 0;
        int root = sequence[len - 1];
        for (; i < len - 1; i ++) {
            if (sequence[i] > root) {
                break;
            }
        }
        int j = i; //i = j = 3
        for (; j < len - 1; j ++) {
            if (sequence[j] < root) {
                return false;
            }
        }
        boolean leftResult = true;
        boolean rightResult = true;
        if (i > 0) {
            int[] left = new int[i];
            for (int k = 0; k < i; k ++) {
                left[k] = sequence[k];
            }
            leftResult = VerifySquenceOfBST(left);
        }
        if (j > 0) {
            int[] right = new int[j];
            for (int k = i; k < j; k ++) {
                right[k] = sequence[k];
            }
            rightResult = VerifySquenceOfBST(right);
        }
        return leftResult && rightResult;
    }
}

注意当右子树中存在小于根的值的时候，那么肯定不是一颗二叉搜索树。