更詳細的講解和代碼調(diào)試演示過程插佛，請參看視頻
用java開發(fā)C語言編譯器
更詳細的講解和代碼調(diào)試演示過程产弹，請參看視頻
如何進入google,算法面試技能全面提升指南
如果你對機器學習感興趣两疚，請參看一下鏈接：
機器學習：神經(jīng)網(wǎng)絡(luò)導(dǎo)論
更詳細的講解和代碼調(diào)試演示過程床估，請參看視頻
Linux kernel Hacker, 從零構(gòu)建自己的內(nèi)核
給定一顆二叉樹如下：
要求把二叉樹的外邊緣按照逆時針的方式打印出來，也就是你需要打印出以下節(jié)點：
314诱渤， 6丐巫， 271， 28勺美， 0递胧， 17， 641赡茸， 257缎脾， 29 ，278占卧， 7
整個二叉樹的外邊緣分三部分遗菠，第一部分是最左邊緣，也就是節(jié)點314华蜒， 6辙纬， 271， 28叭喜。第二部分是底邊節(jié)點贺拣，他們分別是0， 17捂蕴， 641譬涡， 257， 29启绰。第三部分是右邊緣昂儒，他們分別是7， 278.
左邊緣的節(jié)點從根節(jié)點開始委可，一直訪問左孩子渊跋，直到左孩子為空；
底部節(jié)點實際上是二叉樹的所以葉子節(jié)點着倾；
右邊緣節(jié)點是從根節(jié)點開始拾酝，一直訪問右節(jié)點，直到右孩子為空卡者；
根據(jù)以上三種情況蒿囤，通過遍歷二叉樹，獲得三種性質(zhì)的節(jié)點崇决，把他們組合起來就是二叉樹的逆時針外邊緣了材诽。由此代碼實現(xiàn)如下：
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是一個二叉樹節(jié)點隊列底挫，專門用來存儲二叉樹外邊緣的節(jié)點，首先我們通過getLeftSizeNodes來獲取左邊緣的幾點脸侥，它實現(xiàn)方法簡單建邓，只是從跟節(jié)點開始，始終訪問左孩子睁枕，并把他們加入隊列官边。
getBottomSizeNodes用來獲得邊緣的底部節(jié)點，它使用中序遍歷二叉樹節(jié)點外遇，每遍歷一個節(jié)點就判斷其是否是葉子節(jié)點注簿，如果是，則把它加入隊列跳仿，這里要注意的是诡渴，底部節(jié)點與左邊緣節(jié)點有可能會發(fā)送重復(fù)，例如節(jié)點28既是左邊緣節(jié)點塔嬉，也是底部節(jié)點玩徊，因此加入的時候要做個判斷，代碼中的if判斷谨究，作用就是防止把左邊緣和底部邊緣的重合節(jié)點加入隊列兩次。
函數(shù)getRightSizeNodes目的是獲得右邊緣節(jié)點泣棋，這里需要注意的是胶哲，當我們從根節(jié)點開始，依次訪問右孩子時潭辈，所得節(jié)點的次序是順時針的鸯屿，例如從根節(jié)點開始訪問右邊緣節(jié)點是，節(jié)點次序是7把敢， 278寄摆， 29， 但我們需要的是逆時針次序修赞，也就是說婶恼，我們想要的節(jié)點次序是29， 278柏副， 7勾邦，所以在代碼實現(xiàn)中，使用了一個小技巧割择，當獲得右邊緣節(jié)點時眷篇，先將他們壓入堆棧，因為堆棧的特點是后進先出荔泳，壓入堆棧后再把堆棧中的節(jié)點依次彈出蕉饼，這樣的話我們得到的節(jié)點次序就是逆時針的了虐杯。這里還需要注意的一點是，右邊緣節(jié)點和底部節(jié)點有重復(fù)節(jié)點昧港，例如節(jié)點29就是他們的重復(fù)節(jié)點厦幅，代碼中的if判斷就是為了防止把重復(fù)節(jié)點添加兩次。
我們再看看主入口代碼：
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 + " ");
}
}
}
首先我們給定二叉樹的中序遍歷節(jié)點和前序遍歷節(jié)點慨飘，上一節(jié)我們給出了如何根據(jù)兩種節(jié)點次序構(gòu)建二叉樹的算法确憨，構(gòu)建出給定的二叉樹后，把二叉樹的根節(jié)點傳遞給AntiClockWiseTravel瓤的，通過該類獲得一個節(jié)點隊列休弃，這個節(jié)點隊列包含了二叉樹以逆時針次序存放的外部邊緣節(jié)點，上面的代碼運行后得到結(jié)果如下：
314 6 271 28 0 17 641 257 29 278 7
由此可見圈膏，我們的算法準確的以逆時針方式打印了二叉樹的外部邊緣節(jié)點塔猾。
更多技術(shù)信息，包括操作系統(tǒng)稽坤，編譯器丈甸，面試算法，機器學習尿褪，人工智能睦擂，請關(guān)照我的公眾號：
