树 是一种经常用到的数据结构，用来模拟具有树状结构性质的数据集合。
树里的每一个节点有一个根植和一个包含所有子节点的列表。从图的观点来看，树也可视为一个拥有N 个节点和N-1 条边的一个有向无环图。
二叉树是一种更为典型的树树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。
完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;
平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
排序二叉树（二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树）；
树的高度或深度：树中节点的最大层次；
树的度：一棵树中，最大的节点的度称为树的度；
节点的度：一个节点含有的子树的个数称为该节点的度；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
前序遍历
前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。
image.png
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
//递归
public IList<int> PreorderTraversal(TreeNode root) {
List<int> list = new List<int>();
PreOrder(root,list);
return list;
}
public void PreOrder(TreeNode root,List<int> list){
if (root == null) {
return;
}
list.Add(root.val);
PreOrder(root.left,list);
PreOrder(root.right,list);
}
//迭代 本质上是在模拟递归，因为在递归的过程中使用了系统栈，所以在迭代的解法中常用Stack来模拟系统栈。
/*
我们优先将头结点加入Stack，然后加入List,
我们应该先打印左子树，然后右子树。所以先加入Stack的就是右子树，然后左子树。*/
public IList<int> PreorderTraversal(TreeNode root) {
List<int> list = new List<int>();
Stack<TreeNode> stack = new Stack<TreeNode>();
if(root==null){
return list;
}
stack.Push(root);
while(stack.Count!=0){
TreeNode node = stack.Pop();
list.Add(node.val);
if(node.right!=null){
stack.Push(node.right);
}
if(node.left!=null){
stack.Push(node.left);
}
}
return list;
}
中序遍历
中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。
image.png
//递归
public IList<int> InorderTraversal(TreeNode root) {
List<int> list = new List<int>();
Inorder(root,list);
return list;
}
public void Inorder(TreeNode root,List<int> list){
if (root == null) {
return;
}
Inorder(root.left,list);
list.Add(root.val);
Inorder(root.right,list);
}
//迭代 左 中 右
/*
1.尽可能的将这个节点的左子树压入Stack，此时栈顶的元素是最左侧的元素，
其目的是找到一个最小单位的子树(也就是最左侧的一个节点) A B F
2.当处理完最小单位的子树时，返回到上层处理了中间节点。
(左子树->中间(就是一个节点)->右子树)
3.如果有右节点，其也要进行中序遍历。
*/
public IList<int> InorderTraversal(TreeNode root) {
List<int> list = new List<int>();
Stack<TreeNode> stack = new Stack<TreeNode>();
if(root==null){
return list;
}
TreeNode cur = root;
while(stack.Count!=0 || cur !=null){
while(cur!=null){
stack.Push(cur);
cur = cur.left;
}
TreeNode node = stack.Pop();
list.Add(node.val);
if(node.right!=null){
cur = node.right;
}
}
return list;
}
后序遍历
后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。
image.png
//递归
public IList<int> PostorderTraversal(TreeNode root) {
List<int> list = new List<int>();
Postorder(root,list);
return list;
}
public void Postorder(TreeNode root,List<int> list){
if (root == null) {
return;
}
Postorder(root.left,list);
Postorder(root.right,list);
list.Add(root.val);
}
//迭代
/*
1.前序遍历的过程 是 中左右。
2.将其转化成 中右左。也就是压栈的过程中优先压入左子树，在压入右子树。
3.然后将这个结果返回来，这里是利用栈的先进后出倒序打印。
*/
public IList<int> PostorderTraversal(TreeNode root) {
List<int> list = new List<int>();
Stack<TreeNode> stack = new Stack<TreeNode>();
Stack<TreeNode> restack = new Stack<TreeNode>();
if(root==null){
return list;
}
stack.Push(root);
while(stack.Count!=0){
TreeNode node = stack.Pop();
restack.Push(node);
if(node.left!=null){
stack.Push(node.left);
}
if(node.right!=null){
stack.Push(node.right);
}
}
while(restack.Count!=0){
list.Add(restack.Pop().val);
}
return list;
}
Morris解法(不用栈)
image.png
Morris的整体思路就是将以某个根结点开始，找到它左子树的最右侧节点之后与这个根结点进行连接
我们可以从 图2 看到，如果这么连接之后，cur 这个指针是可以完整的从一个节点顺着下一个节点遍历，将整棵树遍历完毕，直到 7 这个节点右侧没有指向。
public static void preOrderMorris(TreeNode head) {
if (head == null) {
return;
}
TreeNode cur1 = head;//当前开始遍历的节点
TreeNode cur2 = null;//记录当前结点的左子树
while (cur1 != null) {
cur2 = cur1.left;
if (cur2 != null) {
while (cur2.right != null && cur2.right != cur1) {//找到当前左子树的最右侧节点，且这个节点应该在指向根结点之前，否则整个节点又回到了根结点。
cur2 = cur2.right;
}
if (cur2.right == null) {//这个时候如果最右侧这个节点的右指针没有指向根结点，创建连接然后往下一个左子树的根结点进行连接操作。
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {//当左子树的最右侧节点有指向根结点，此时说明我们已经回到了根结点并重复了之前的操作，同时在回到根结点的时候我们应该已经处理完 左子树的最右侧节点 了，把路断开。
cur2.right = null;
}
}
cur1 = cur1.right;//一直往右边走，参考图
}
}
