算法面试题：逆时针打印二叉树外围边缘
更详细的讲解和代码调试演示过程，请参看视频
用java开发C语言编译器
更详细的讲解和代码调试演示过程，请参看视频
如何进入google,算法面试技能全面提升指南
如果你对机器学习感兴趣，请参看一下链接：
机器学习：神经网络导论
更详细的讲解和代码调试演示过程，请参看视频
Linux kernel Hacker, 从零构建自己的内核
给定一颗二叉树如下：
这里写图片描述
要求把二叉树的外边缘按照逆时针的方式打印出来，也就是你需要打印出以下节点：
314， 6， 271， 28， 0， 17， 641， 257， 29 ，278， 7
整个二叉树的外边缘分三部分，第一部分是最左边缘，也就是节点314， 6， 271， 28。第二部分是底边节点，他们分别是0， 17， 641， 257， 29。第三部分是右边缘，他们分别是7， 278.
左边缘的节点从根节点开始，一直访问左孩子，直到左孩子为空；
底部节点实际上是二叉树的所以叶子节点；
右边缘节点是从根节点开始，一直访问右节点，直到右孩子为空；
根据以上三种情况，通过遍历二叉树，获得三种性质的节点，把他们组合起来就是二叉树的逆时针外边缘了。由此代码实现如下：
import java.util.ArrayList;
import java.util.Stack;
public class AntiClockWiseTravel {
private ArrayList<TreeNode> antiClockWiseNodeList = new ArrayList<TreeNode>();
private TreeNode root;
private void getLeftSizeNodes() {
TreeNode node = root;
while (node != null) {
antiClockWiseNodeList.add(node);
node = node.left;
}
}
private void inorder(TreeNode node) {
if (node == null) {
return;
}
inorder(node.left);
if (node.left == null && node.right == null) {
if (antiClockWiseNodeList.get(antiClockWiseNodeList.size() - 1) != node) {
antiClockWiseNodeList.add(node);
}
return;
}
inorder(node.right);
}
private void getBottomSizeNodes() {
TreeNode node = root;
inorder(node);
}
private void getRightSizeNodes() {
TreeNode node = root;
Stack<TreeNode> stack = new Stack<TreeNode>();
node = node.right;
while (node != null) {
stack.push(node);
node = node.right;
}
while (stack.empty() != true) {
TreeNode n = stack.pop();
if (antiClockWiseNodeList.get(antiClockWiseNodeList.size() - 1 ) != n) {
antiClockWiseNodeList.add(n);
}
}
}
public AntiClockWiseTravel(TreeNode root) {
this.root = root;
getLeftSizeNodes();
getBottomSizeNodes();
getRightSizeNodes();
}
public ArrayList<TreeNode> getAntiClockWiseNodes() {
return antiClockWiseNodeList;
}
}
antiClockWiseNodeList是一个二叉树节点队列，专门用来存储二叉树外边缘的节点，首先我们通过getLeftSizeNodes来获取左边缘的几点，它实现方法简单，只是从跟节点开始，始终访问左孩子，并把他们加入队列。
getBottomSizeNodes用来获得边缘的底部节点，它使用中序遍历二叉树节点，每遍历一个节点就判断其是否是叶子节点，如果是，则把它加入队列，这里要注意的是，底部节点与左边缘节点有可能会发送重复，例如节点28既是左边缘节点，也是底部节点，因此加入的时候要做个判断，代码中的if判断，作用就是防止把左边缘和底部边缘的重合节点加入队列两次。
函数getRightSizeNodes目的是获得右边缘节点，这里需要注意的是，当我们从根节点开始，依次访问右孩子时，所得节点的次序是顺时针的，例如从根节点开始访问右边缘节点是，节点次序是7， 278， 29， 但我们需要的是逆时针次序，也就是说，我们想要的节点次序是29， 278， 7，所以在代码实现中，使用了一个小技巧，当获得右边缘节点时，先将他们压入堆栈，因为堆栈的特点是后进先出，压入堆栈后再把堆栈中的节点依次弹出，这样的话我们得到的节点次序就是逆时针的了。这里还需要注意的一点是，右边缘节点和底部节点有重复节点，例如节点29就是他们的重复节点，代码中的if判断就是为了防止把重复节点添加两次。
我们再看看主入口代码：
import java.util.ArrayList;
public class BinaryTree {
public static void main(String[] s) {
int[] inorder = new int[]{28, 271, 0, 6, 561, 17, 3, 314, 2, 401, 641, 1, 257, 7, 278, 29};
int[] preorder= new int[] {314, 6, 271, 28, 0, 561, 3, 17, 7, 2, 1, 401, 641, 257, 278, 29};
BTreeBuilder treeBuilder = new BTreeBuilder(inorder, preorder);
TreeNode root = treeBuilder.getTreeRoot();
PrintTreeList pt = new PrintTreeList(root);
pt.printTree();
System.out.print("\n");
AntiClockWiseTravel at = new AntiClockWiseTravel(root);
ArrayList<TreeNode> list = at.getAntiClockWiseNodes();
for (int i = 0; i < list.size(); i++) {
TreeNode n = list.get(i);
System.out.print(n.val + " ");
}
}
}
首先我们给定二叉树的中序遍历节点和前序遍历节点，上一节我们给出了如何根据两种节点次序构建二叉树的算法，构建出给定的二叉树后，把二叉树的根节点传递给AntiClockWiseTravel，通过该类获得一个节点队列，这个节点队列包含了二叉树以逆时针次序存放的外部边缘节点，上面的代码运行后得到结果如下：
314 6 271 28 0 17 641 257 29 278 7
由此可见，我们的算法准确的以逆时针方式打印了二叉树的外部边缘节点。
更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号：
这里写图片描述
