引子：五分钟玩转面试考点-数据结构系列，不会像那种严肃、古板的教科书般的博客文章，而是将晦涩难懂的概念和知识点尽可能幽默的细说出来，或结合生活场景，或从零开始分析。带给大家一个严肃而不失风趣的数据结构。
向上的路，其实并不拥挤，拥挤是因为，大部分人选择了安逸...
这几天练了一下数据结构的算法，脑袋疼，而且整的我有点怀疑人生了...
那废话不多说，咱们进行练习吧。
1、操作给定的二叉树，将其变换为源二叉树的镜像（二叉树左右节点交换位置）。
说实话，拿到这道题的时候，我脑子里就想到了层级遍历。层级遍历使用的是队列，可以一层一层的处理数据。
public void Mirror(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (queue.size() != 0) {
//小世界
TreeNode pollNode = queue.poll();
TreeNode lRoot = pollNode.left;
pollNode.left = pollNode.right;
pollNode.right = lRoot;
if (pollNode.left != null)
queue.offer(pollNode.left); //左边保存
if (pollNode.right != null)
queue.offer(pollNode.right); //右边保存
}
}
原理就是：使用一个队列queue，将根节点保存到队列中，然后将根节点取出之后，获取左右两子树后，然后交换位置。再放入队列中。
public void Mirror(TreeNode root) {
//递归出口
if (root == null) {
return;
}
//递归逻辑(交换)
TreeNode tempNode = root.left;
root.left = root.right;
root.right = tempNode;
//先统一处理左子树，在统一处理右子树，在处理右子树。
Mirror(root.left);
Mirror(root.right);
}
于是我就问自己，如何才能使用递归将这个代码写出来呢？
递归出口：程序在极端情况下的返回，一般需要终止递归调用代码；
递归返回值：程序运行一次到底想要返回什么值。我们使用递归。明显就是拿到返回值之后再进行算法处理。
内部逻辑：每一次方法调用要执行的逻辑操作，会影响递归的返回值。
极端情况？
若是参数为null，那么直接返回；
返回值为void？
那么我们要考虑，我们内部的逻辑是什么？
我们其实是使用的前序遍历的思想。第一次获取根节点的时候，将左右子树反转，第二次获取根节点...第三次获取根节点...小胖有点蒙了，我反转了3次？PS：我是不是有点傻~第三次获取根节点的时候反转左右子树就可以啦 后序遍历。
public void Mirror(TreeNode root) {
//递归出口
if (root == null) {
return;
}
//递归逻辑(交换)
//先统一处理左子树，在统一处理右子树，在处理右子树。
Mirror(root.left);
Mirror(root.right);
TreeNode tempNode = root.left;
root.left = root.right;
root.right = tempNode;
}
2、求树的深度？
首先咱们要明白，树的高度=左右两子树最大高度+1。
极端情况？
如果上送的是null，那么直接返回0；
返回值为int？树的最大高度？
计算高度，我们要访问左子树，求左子树的最大高度；在访问右子树，求右子树的最大高度，最后将最大高度+1。后序遍历。左子树也是一棵树，右子树也是一棵树。
public int TreeDepth(TreeNode root) {
//递归出口
if (root == null) {
return 0;
}
//逻辑运算
int leftDepth = TreeDepth(root.left); //左子树高度
int rightDepth = TreeDepth(root.right); //右子树高度
return 1+Math.max(leftDepth, rightDepth); //返回左右子树最大值
}
非递归就是层级遍历，每次指针到底同层的最右元素时，将队列长度保存起来（下一层的最大宽度，然后高度+1，指针清0）。
public int TreeDepth(TreeNode root) {
//层级遍历，每一层遍历完毕，在遍历下一层；
//在每一层最右元素的位置时，队列里面保存的是下一层所有节点数,
// 每遍历一个元素count++，若是最后一个元素nextCount++，此时depthCount++
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int count = 0; //指针位置[0-curCount]
int curCount = 1; //当前节点总个数
int depthCount = 0; //层级深度
while (queue.size() != 0) {
count++; //没运行一次，指针加一
TreeNode treeNode = queue.poll(); //取出头结点
if (treeNode.left != null)
queue.offer(treeNode.left);
if (treeNode.right != null)
queue.offer(treeNode.right);
//当层级-最右元素poll出来之后，
if (count == curCount) {
count = 0; //指针恢复出厂设置
curCount = queue.size(); //当前层级设置为下一级
depthCount++; //深度+1
}
}
return depthCount;
}
