第一题：
确定两点：
1）n个数，即n个节点，能构造出多少种不同形态的树？
2）n个数，有多少种不同的排列？
当确定以上两点，将【1)的结果】乘以 【2)的结果】，即为最终的结果。
但是有一个注意的点： 如果n中有相等的数，产生的总排列数就不是n！了哟

通过这一题，我学到了【卡塔兰数】：https://en.wikipedia.org/wiki/Catalan_number

第二题：
层序遍历，借用队列辅助即可，根节点先入队列，然后循环从队列中pop节点，将pop出来的节点的左子节点先入队列，右节点后入队列，依次循环，直到队列为空，遍历结束。

leetcode上有个类似的题目，链接为：https://leetcode.com/problems/binary-tree-level-order-traversal/
Java代码如下：
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<>(0);
        
        List<List<Integer>> result = new ArrayList<>();
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        Queue<TreeNode> curLevelNodes = new LinkedList<TreeNode>();
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            curLevelNodes.offer(node);
            
            if (queue.isEmpty()) {
                List<Integer> list = new ArrayList<>(curLevelNodes.size());
                while (!curLevelNodes.isEmpty()) {
                    TreeNode curNode = curLevelNodes.poll();
                    list.add(curNode.val);
                    
                    if (curNode.left != null) {
                        queue.offer(curNode.left);
                    }
                    
                    if (curNode.right != null) {
                        queue.offer(curNode.right);
                    }
                    
                }
                result.add(list);
            }
        }
        
        
        return result;
    }
    
}

树，总共包含4节内容。具体如下：
1.树、二叉树
2.二叉查找树
3.平衡二叉树、红黑树
4.递归树

一、树
1.树的常用概念
根节点、叶子节点、父节点、子节点、兄弟节点，还有节点的高度、深度以及层数，树的高度。
2.概念解释
节点：树中的每个元素称为节点
父子关系：相邻两节点的连线，称为父子关系
根节点：没有父节点的节点
叶子节点：没有子节点的节点
父节点：指向子节点的节点
子节点：被父节点指向的节点
兄弟节点：具有相同父节点的多个节点称为兄弟节点关系
节点的高度：节点到叶子节点的最长路径所包含的边数
节点的深度：根节点到节点的路径所包含的边数
节点的层数：节点的深度+1（根节点的层数是1）
树的高度：等于根节点的高度
二、二叉树
1.概念
①什么是二叉树？
每个节点最多只有2个子节点的树，这两个节点分别是左子节点和右子节点。
②什么是满二叉树？
有一种二叉树，除了叶子节点外，每个节点都有左右两个子节点，这种二叉树叫做满二叉树。
③什么是完全二叉树？
有一种二叉树，叶子节点都在最底下两层，最后一层叶子节都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。
2.完全二叉树的存储
①链式存储
每个节点由3个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式比较常用，大部分二叉树代码都是通过这种方式实现的。
②顺序存储
用数组来存储，对于完全二叉树，如果节点X存储在数组中的下标为i，那么它的左子节点的存储下标为2*i，右子节点的下标为2*i+1，反过来，下标i/2位置存储的就是该节点的父节点。注意，根节点存储在下标为1的位置。完全二叉树用数组来存储时最省内存的方式。
3.二叉树的遍历
①前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
②中序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的本身，最后打印它的右子树。
③后序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印它本身。
前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
时间复杂度：3种遍历方式中，每个节点最多会被访问2次，所以时间复杂度是O(n)。
三、思考
1.二叉树有哪几种存储方式？什么样的二叉树适合用数组来存储？
2.给定一组数据，比如1，3，5，6，9，10.你来算算，可以构建出多少种不同的二叉树？
3.我们讲了三种二叉树的遍历方式，前、中、后序。实际上，还有另一种遍历方式，也就是按层遍历，你知道如何实现吗？
4.如何用循环实现二叉树的遍历？

/**
     * 层次遍历二叉树
     *
     * @param root
     */
    public static void levelOrder(Node root) {
        if (root == null) {
            return;
        }
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node currentNode = queue.poll();
            System.out.print(currentNode.getValue() + " ");
            if (currentNode.getLeft() != null) {
                queue.add(currentNode.getLeft());
            }
            if (currentNode.getRight() != null) {
                queue.add(currentNode.getRight());
            }
        }
    }

思考题：
1. 一组数能构建多少个二叉树？
第一时间想到只要排列位置有改变，那么就应该是新的二叉树。组合排列的公式有点忘记了。。。那么用笨方法：
当只有1个数的时候，能构建1个二叉树；2个数时是2个二叉树；3个数有6个二叉树；再看下4个数，原来是24个；最后得出n!
2. 层序遍历二叉树：
数组和链表的方式都一样。先打印本身的数据，然后将左右节点塞到一个队列中；从队列里取第一个节点打印数据，并将其左右节点再塞到队列，以此类推。

public static void leverOrder(Node n) {
    Queue<Node> queue = new Queue<>();
    queue.enqueue(n);
    while (!queue.isEmpty()) {
      Node p = queue.dequeue();
      StdOut.println(p);
      if (p.left != null) {
        queue.enqueue(p.left);
      }
      if (p.right != null) {
        queue.enqueue(p.right);
      }
    }
  }