二叉树概念
二叉树：每个结点最多有两个子树的树结构。
满二叉树：一棵深度为k，且有2^k-1个结点的二叉树。
完全二叉树：一棵二叉树中，除最后一层外，若其余层都是满的。并且最后一层或者是满的，或者是在右边缺少连续若干结点。
满二叉树和完全二叉树
平衡二叉树（Balanced Binary Tree）：或者是一棵空树，或者任一树节点的左右两个子树的高度差的绝对值不超过1。
二叉查找树（二叉搜索树）（Binary Search Tree）：对于树中的每个节点X，它的左子树中所有项的值小于X中的项，而它的右子树中所有项的值大于X中的项。
前序、中序、后序和分层遍历
二叉树节点定义
public class TreeNode {
private int code;
private TreeNode left;
private TreeNode right;
TreeNode(int code) {
this.code = code;
}
public int getCode() {
return code;
}
public void setCode(int code) {
this.code = code;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
前序遍历
首先访问根结点然后遍历左子树，最后遍历右子树。
递归实现
递归实现最简单，也最容易阅读。先访问根节点，然后分别递归调用左子树和右子树即可。
public void recursion(TreeNode root, List<Integer> list){
if (root == null){
return;
}
list.add(root.getCode());
recursion(root.getLeft(), list);
recursion(root.getRight(), list);
}
非递归（迭代）实现
迭代实现比较难以理解。本质上就是模拟递归实现栈的存储过程。
- 沿着左子树向下访问到叶子节点；
- 从栈中取出栈顶元素，向右转弯，执行1逻辑。
直到访问了所有节点为止。
public void interation(TreeNode root, List<Integer> list){
if (root == null){
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
while(root != null){
while (root != null){
list.add(root.getCode());
stack.push(root);
root = root.getLeft();
}
while (!stack.empty() && root == null){
root = stack.pop();
root = root.getRight();
}
}
}
中序遍历
首先遍历左子树，然后访问根结点，最后遍历右子树
递归实现
public void recursion(TreeNode root, List<Integer> list){
if (root == null){
return;
}
recursion(root.getLeft(), list);
list.add(root.getCode());
recursion(root.getRight(), list);
}
非递归（迭代）实现
与前序遍历相似，只是访问节点时机不同。中序遍历在右转之前访问，保证节点的访问在左子树之后，右子树之前。
- 沿着左子树向下访问到叶子节点；
- 访问栈顶元素，向右转弯，执行1逻辑。
public void interation(TreeNode root, List<Integer> list){
if (root == null){
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
while(root != null){
while (root != null){
stack.push(root);
root = root.getLeft();
}
while (!stack.empty() && root == null){
root = stack.pop();
list.add(root.getCode());
root = root.getRight();
}
}
}
后序遍历
首先遍历左子树，然后遍历右子树，最后访问根结点。
递归实现
public void recursion(TreeNode root, List<Integer> list){
if (root == null){
return;
}
recursion(root.getLeft(), list);
recursion(root.getRight(), list);
list.add(root.getCode());
}
非递归（迭代）实现
后序遍历的迭代实现又分为单栈实现和双栈实现
单栈实现
单栈实现就是在遍历过程中使用一个栈
- 沿着左子树向下访问到叶子节点。
- 栈顶元素出栈，判断是否存在右子树：若存在，当前节点重复入栈，并且其right引用置null，以免下次出栈再次遍历其右子树；若不存在，访问当前节点。
- 右转弯到右子树上，回到第1步或2步。
public void interation(TreeNode root, List<Integer> list){
if (root == null){
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
while(root != null){
while (root != null){
stack.push(root);
root = root.getLeft();
}
while (!stack.empty() && root == null){
root = stack.pop();
TreeNode right = root.getRight();
if (right == null){
list.add(root.getCode());
} else {
stack.push(root);
root.setRight(null);
}
root = right;
}
}
}
双栈实现
双栈实现代码比单栈实现要简洁，好记忆。最好的理解方法是拿出纸笔按照下面的代码画出两个栈中节点的进出情况。stack1用于规划下一个将要访问的节点，stack2保存后序遍历节点访问的顺序。
public void interation2(TreeNode root, List<Integer> list){
if (root == null){
return;
}
Stack<TreeNode> stack1 = new Stack<TreeNode>();
Stack<TreeNode> stack2 = new Stack<TreeNode>();
stack1.push(root);
while(!stack1.empty()){
//下一个访问的节点
root = stack1.pop();
stack2.push(root);
//先入栈左子树节点
if (null != root.getLeft()){
stack1.push(root.getLeft());
}
//再入栈右子树节点，这样下一个访问的将是右子树
if (null != root.getRight()){
stack1.push(root.getRight());
}
}
//stack2元素出栈顺序即是后序遍历顺序
while (!stack2.empty()){
list.add(stack2.pop().getCode());
}
}
一个树遍历的例子——表达式树（expression tree）
如下图所示就是一个表达式树，叶子节点是操作数（operand），其他节点是操作符（operator）。
(a + b * c) + ((d * e + f) * g)的表达式树
表达式(a + b * c) + ((d * e + f) * g)可以分为前缀、中缀和后缀表示。
- 后缀表示（即表达式树的后序遍历结果）：abc+def+g*+
- 前缀表示（即表达式树的前序遍历结果）：++abc+*defg
- 中缀表示（即表达式树的中序遍历结果）：(a+bc)+((de+f)*g)
分层遍历
分层遍历同样分为递归实现和迭代实现两种方式，代码如下：
递归实现
/**
*
* @param root 树节点
* @param level 递归当前遍历的层级
* @param list 分层保存遍历的树的节点，例如：根节点保存在list.get(0)返回的队列中
*/
public void recursion(TreeNode root, int level, List<List<Integer>> list){
if (null == root){
return;
}
//如果list中元素等于当前递归层级，表明需要初始化一个新的list。层级从0开始。
if (level == list.size()){
list.add(level, new ArrayList<Integer>());
}
//遍历当前节点
list.get(level).add(root.getCode());
//递归当前节点的左右子树
recursion(root.getLeft(), level + 1, list);
recursion(root.getRight(), level + 1, list);
}
迭代实现
/**
*
* @param root
* @param list 分层保存遍历的树的节点，例如：根节点保存在list.get(0)返回的队列中
*/
public void interation(TreeNode root, List<List<Integer>> list){
if (root == null){
return;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);//树根节点先入队
int level = 0;//从第0层开始
while(!queue.isEmpty()){
int size = queue.size();//当前层级节点个数
List<Integer> l = new ArrayList<Integer>();
for (int i = 0; i < size; ++i){//遍历当前层级的节点
TreeNode node = queue.poll();
l.add(node.getCode());//节点入队
if (node.getLeft() != null){
queue.add(node.getLeft());//左子树入队
}
if (node.getRight() != null){
queue.add(node.getRight());//右子树入队
}
}//for循环结束，此时当前层级节点遍历完成，队列中剩余的是level+1层级的节点
list.add(level, l);
level++;//层级加1
}
}
二叉搜索树
AVL Tree
红黑树
二叉树算法例题
二叉搜索树不同组合
验证二叉搜索树
恢复二叉搜索树
判断两棵二叉树是否相同
对称二叉树
层次遍历二叉树
前序（后序）与中序遍历确定一棵二叉树
求二叉树的深度
判断二叉树是否是平衡二叉树
二叉树路径节点关键值和等于目标值
二叉树中的最大路径和
