参考博客：
https://blog.csdn.net/My_Jobs/article/details/43451187
https://blog.csdn.net/qq_37859539/article/details/81462171
嗯，最近做的题都是关于二叉树的，leetcode大概从94开始一直到114差不多都是关于二叉树，二叉查找树的。这些题大多是需要在遍历的基础上做修改。
深度遍历：前序、中序、后序（递归实现）
广度遍历：层次遍历（需要其他数据结构的支持，比如堆）
四种主要的遍历思想为：
前序遍历：根结点 ---> 左子树 ---> 右子树
中序遍历：左子树---> 根结点 ---> 右子树
后序遍历：左子树 ---> 右子树 ---> 根结点
层次遍历：只需按层次遍历即可
前序：1 2 4 5 7 8 3 6
中序：4 2 7 5 8 1 3 6
后序：4 7 8 5 2 6 3 1
层次：1 2 3 4 5 6 7 8
代码：
前序递归：
public void preOrderTraversel(TreeNode root){
if(root != null){
System.out.print(root.val + " ");
preOrderTraversel(root.left);
preOrderTraversel(root.right);
}
}
前序非递归：
根据前序遍历的顺序，优先访问根结点，然后在访问左子树和右子树。所以，对于任意结点node，第一部分即直接访问之，之后在判断左子树是否为空，不为空时即重复上面的步骤，直到其为空。若为空，则需要访问右子树。注意，在访问过左孩子之后，需要反过来访问其右孩子，所以，需要栈这种数据结构的支持。对于任意一个结点node，具体步骤如下：
a)访问之，并把结点node入栈，当前结点置为左孩子；
b)判断结点node是否为空，若为空，则取出栈顶结点并出栈，将右孩子置为当前结点；否则重复a)步直到当前结点为空或者栈为空（可以发现栈中的结点就是为了访问右孩子才存储的）
栈中内容：1 2 4 -> 1 2 -> 1 -> 1 5 7 -> 1 5 -> 1 -> 1 8 -> 1 -> null -> 3 -> null -> 6 -> null
在入栈时打印值为前序，出栈时打印为中序。
public viod preOrderTraversel(TreeNode root){
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode pNode = root;
while(pNode != null || !stack.isEmpty()){
if(pNode != null){
System.out.print(pNode.val + " ");
stack.push(pNode);
pNode = pNode.left;
}else{
TreeNode node = stack.pop();
pNode = node.right;
}
}
}
中序递归：
public void inOrderTraversel(TreeNode root){
if(root != null){
inOrderTraversel(root.left);
System.out.print(root.val + " ");
inOrderTraversel(root.right);
}
}
中序非递归：只不过访问的顺序移到出栈时
public void inOrderTraversel(TreeNode root){
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode pNode = root;
while(pNode != null || !stack.isEmpty()){
if(pNode != null){
stack.push(pNode);
pNode = pNode.left;
}else{
TreeNode node = stack.pop();
System.out.print(node.val + " ");
pNode = node.right;
}
}
}
后序递归：
public void postOrderTraversel(TreeNode root){
postOrderTraversel(root.left);
postOrderTraversel(root.right);
System.out.print(root.val + " ");
}
后序非递归：
//在前序遍历中将中 左 右 压栈
//在原来打印的地方不打印，将本该被打印的地方压到第二个栈中
//这样第二个栈的出栈顺序顺序就是 左 右 中
入栈1的时候先入左孩子，则右孩子会先pop出来压入栈2，这样栈2的入栈顺序就是中 右 左，全部入栈之后pop出来就是后序遍历了。
public void postOrderTraversel(TreeNode root){
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<TreeNode> stack2 = new LinkedList<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
stack2.push(node);
if(node.left != null){
stack.push(node.left);
}
if(node.right != null){
stack.push(node.right);
}
}
while(!stack2.isEmpty()){
System.out.print(stack2.pop().val + " ");
}
}
层次遍历：
用队列，先入先出
public void levelTraversel(TreeNode root){
if(root == null){
return;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
}
这个是按照层次遍历的顺序给定一组数，然后建立对应二叉树的方法：
因为想要在自己本地的环境下做测试嘛，可以调试找错误，就写了这种建立二叉树的方法，应该是最简单的一种。
这里因为某结点的左孩子或者右孩子都有可能是null（null可以是任意类的对象），所有输入不能数组，而应该是Integer的list。
public TreeNode build(List<Integer> s){
LinkedList<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode(s.get(0));
queue.offer(root);
int i = 1;
while(i < s.size()){
TreeNode pNode = queue.poll();
if(pNode == null){
i++;
continue;
}else{
Integer vall = s.get(i++);
if(vall != null){
pNode.left = new TreeNode(vall);
}else{
pNode.left = null;
}
queue.offer(pNode.left);
if(i == s.size()){
pNode.right = null;
}else{
Integer valr = s.get(i++);
if(valr != null){
pNode.right = new TreeNode(valr);
}else{
pNode.right = null;
}
}
queue.offer(pNode.right);
}
}
return root;
}
下面这个是对结点的定义：
public class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x;}
}
二叉查找树（binary search tree）: 二叉查找树，也称为二叉搜索树、有序二叉树或排序二叉树，是指一棵空树或者具有下列性质的二叉树： 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 任意节点的左、右子树也分别为二叉查找树； 没有键值相等的节点