1. 二叉树的数据结构
public class TreeNode {
public int val;
public TreeNode left; //左子树
public TreeNode right; //右子树
public TreeNode(int x) { val = x; }
}
2. 遍历
二叉树的遍历方式有二种：
- 深度优先遍历，主要包括：前序遍历、中序遍历、后序遍历；
- 广度优先遍历，主要包括：层次遍历
2.1 前序遍历
思路：根-左-右
2.1.1 递归
public static void queryPreByDg(TreeNode node){
if(node == null){
return;
}
//打印根节点
System.out.println(node.val);
//遍历左子树
queryPre(node.left);
//遍历右子树
queryPre(node.right);
}
2.1.2 非递归
思路：使用stack的特性
- 栈顶出来，即为cur
- 有右压入右，有左压入左，那么出栈一定是先左后右
public static void queryPre(TreeNode node){
if(node == null){
return;
}
//根节点先入栈
TreeNode cur = node;
Stack<TreeNode> stack = new Stack<>();
stack.add(cur);
while (!stack.isEmpty()){
TreeNode popNode = stack.pop();
//打印根节点
System.out.println(popNode.val);
//有右压入右
if(popNode.right!=null){
stack.add(popNode.right);
}
//有左压入左
if(popNode.left!=null){
stack.add(popNode.left);
}
}
}
2.2 中序遍历
思路：左-根-右
2.2.1 递归
public static void queryMidByDg(TreeNode node){
if(node == null){
return;
}
//遍历左子树
queryPre(node.left);
//打印根节点
System.out.println(node.val);
//遍历右子树
queryPre(node.right);
}
2.2.2 非递归
思路：
- 当前节点cur，cur为头的整个左边界进栈，直到遇到空 -》2
- 从栈中弹出节点打印，节点的右孩子成为cur回 -》1
- 栈为空停
public static void queryMid(TreeNode node){
if(node == null){
return;
}
//将以根节点的左边界入栈
TreeNode cur = node;
Stack<TreeNode> stack = new Stack<>();
while (cur!=null){
stack.add(cur);
cur = cur.left;
}
//开始出栈，从最左边的节点
while (!stack.isEmpty()){
TreeNode popNode = stack.pop();
//打印节点
System.out.println(popNode.val);
//将节点的右孩子的左边界入栈
if(popNode.right!=null){
cur = popNode.right;
while (cur!=null){
stack.add(cur);
cur = cur.left;
}
}
}
}
2.3 后序遍历
思路：左-右-根，递归和非递归的方式可以参考前序遍历
理论上还可以有：根-右-左，右-根-左，右-左-根 这些遍历的方式
2.4 层次遍历
2.4.1 普通层次遍历
思路：可以使用队列实现
public List<Integer> levelQuery(TreeNode root,List<Integer> list){
//头节点入队
TreeNode node = root;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(node);
while(queue.size()>0){
//根结点出队，记录
node = queue.poll();
list.add(node.val);
//左孩子入队列
if(node.left!=null){
queue.add(node.left);
}
//右孩子入队列
if(node.right!=null){
queue.add(node.right);
}
}
return list;
}
2.4.2 Z层次遍历
思路：
- 每层需要记录层数
- 偶数层从左边遍历，期数层从右开始遍历，
整体有2种实现方式，分别为：双端队列；栈 + 队列实现
详情见：http://www.wyjblog.com/archives/103%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%94%AF%E9%BD%BF%E5%BD%A2%E5%B1%82%E6%AC%A1%E9%81%8D%E5%8E%86
3. 构建
根据二叉树的特性可知：
要想确定一个树，至少需要知道「中序」和 「前序后序中的一种」，即：
- 中序 + 前序
- 中序 + 后序
3.1 根据前序和中序构建二叉树
思路：
- 由前序遍历的特点可知第一个节点一定是根节点
- 在中序遍历中，左孩子一定在根节点的前index，后孩子一定在根节点的后面index
所以： - 遍历前序序列
- 获取当前 前序节点在中序遍历上的位置和根节点的在中序遍历的位置，比较
- 如果小于，在左树，如果左树根节点为空直接插入即可，如果不为空，继续比较和当前左树根节点的位置，继续找位置
- 如果大于，在右树，如果右树根节点为空直接插入即可，如果不为空，继续比较和当前右树根节点的位置，继续找位置
public static TreeNode buildTreeByPreAndMid(int[] preList, int[] midList){
TreeNode root= null;
//遍历前序序列
for (int i = 0; i < preList.length; i++) {
root = insert(root,preList[i],midList);
}
return root;
}
public static TreeNode insert(TreeNode root, int data, int[] midList){
//新建立的结点
TreeNode p = new TreeNode(data);
if(root == null){
root = p;
}else{
//该结点用来遍历
TreeNode node = root;
int pos = getPosInMid(data,midList);
while(true){
int rootPos = getPosInMid(node.val,midList);
//在左树中
if(pos<rootPos){
//如果左树有节点了，继续寻找位置
if(node.left!=null){
node = node.left;
}else{
//左结点为null插入。
node.left = p;
break;
}
}else{
//在右树中，右树有节点了，继续寻找位置
if(node.right!=null){
node = node.right;
}else{
//右结点为null插入。
node.right = p;
break;
}
}
}
}
return root;
}
//获取前序节点在中序序列上的index
public static int getPosInMid(int data, int[] midList){
for (int i = 0; i < midList.length; i++) {
if(midList[i] == data){
return i;
}
}
return 0;
}
