轉載自??qing的世界 ?程序員小樂

文章目錄

• 前言

• 二叉樹的遞歸（深度優先）處理

• 二叉樹的層序處理(廣度優先)

• 總結

“

?一、前言

今年可謂是跌宕起伏的一年，幸好結局還算是圓滿。開年的時候由于和公司CTO有過節，被"打入冷宮"，到下半年開始找工作，過程還是蠻艱辛。先分享一下offer的情況

國內的有

1.阿里口碑(offer)
2.Wish(offer)
3.Booking(Offer)
4.今日頭條(Offer)
5.Airbnb(北京)被拒

最讓我開心的是拿到了硅谷的offer！

FaceBook Menlo Park總部的offer
Amazon 西雅圖總部 offer

在面試的過程中我深深的感受到，對于一個優秀的安卓開發來說，首先擺在第一位的還是他/她作為一個軟件工程師的基本素養。無論你是做前端還是后端，最后定義你的優秀程度的還是作為軟件工程師的基本素養，學習能力和編程能力，還有設計能力。我自己在現在的公司也做過面試官，發現新加坡的大部分碼農(東南亞的碼農)，對基礎的編程能力實在是有所欠缺，熟練的使用API卻不能理解為什么。

很多同學會在長久以往的業務邏輯開發中慢慢迷失，逐漸的把寫代碼變成了一種習慣，而沒有再去思考自己代碼的優化，結構的調整。這個現象不止是安卓開發的小伙伴有，任何大公司的朋友都會遇到。所以我這一系列的文章打算深入的講解一下對于安卓程序員面試中可能遇到的算法。也希望能培養大家多思考，業余時間多動手寫好代碼，優質代碼的習慣。

那么第一篇我打算著重講一下二叉樹的問題。

一、二叉樹的遞歸（深度優先）處理

“

?二、二叉樹的遞歸（深度優先）處理

相信大家以前在學習算法與數據結構的時候都遇到過。比如說，打印二叉樹前序，中序，后序的字符串這種問題。一般來說我們會選擇使用遞歸的形式來打印，比如說

/**
** 二叉樹節點
**/
public class TreeNode{
? ?TreeNode left;
? ?TreeNode Right;
? ?int value;
}
//中序
public void printInoderTree(TreeNode root){
? ?//base case
? ?if(root == null){
? ? ? ?return;
? ?}
? ?//遞歸調用printTree
? ?printInoderTree(root.left);
? ?System.out.println(root.val);
? ?printInoderTree(root.right);
}
//中序
public void printPreoderTree(TreeNode root){
? ?//base case
? ?if(root == null){
? ? ? ?return;
? ?}
? ?//遞歸調用printTree
? ?System.out.println(root.val);
? ?printPreoderTree(root.left);
? ?printPreoderTree(root.right);
}

一開始上學的時候，我這幾段代碼都是背下來的，完全沒有理解其中的奧妙。對于二叉樹的遞歸操作，其實正確的理解方式

把每次遞歸想象成對其子集(左右子樹)的一個操作，假設該遞歸已經可以處理好左右子樹，那么根據已經處理好的左右子樹在調整根節點。

這樣的思想其實和分而治之 分治法 相似，就是把一個大問題先分成小問題，再去解決。我們還是以二叉樹的中序打印為例子。

因為中序打印我們需要以左中右的順序打印二叉樹，以下圖為例子我們分解一下問題。

上面這個gif詳細的解釋了怎么叫分而治之，首先，我們假設A節點的左右子樹分開而且已經打印完畢，那么只剩下A節點需要單獨處理，那么久打印它。對于B子樹來說，我們以同樣的思維處理。所以動圖里面是B子樹先鋪平，然后輪到A節點，最后到C子樹。

最后我們需要考慮一下這個遞歸的結束條件。我們假設A節點左右子樹都為空，null,那么在調用該方法的時候我們需要在Node為空的時候直接返回不做任何操作。該條件我們一般稱為遞歸的Base Case。每個遞歸都是這樣，先想好我們怎么把問題分治， 再考慮base case是哪些，怎么處理，我們的遞歸就結束了。

問題來了，我們明明要講深度優先，為什么講起遞歸了。兩者的聯系是什么？

其實遞歸對于很多數據結構來說，就是深度優先，比如二叉樹，圖。因為在遞歸的過程中，我們就是在一層一層的往下走，比如對于二叉樹的中序打印來說，我們遞歸樹的左節點，除非左節點為空，我們會一直往下走，這本身就是深度優先了。所以一般來說，對于深度優先，我們都會用遞歸來解決，因為寫起來最方便。當然我們深度優先如果不想用遞歸，還可以使用棧(Stack)來解決，我們在以后的文章來講(不過大家需要知道的是，遞歸本身就是使用方法棧的一種操作，聯想一下我們常常聽到的StackOverFlow,你應該能明白其中的奧妙了吧)。

好！相信我已經勾起了大家對大學算法課的記憶了！那么我們來鞏固一下。使用分治思想+遞歸，我們就已經可以解決大部分二叉樹的問題了。 我們來看一道題目->

1. 翻轉二叉樹

這道題是一個經典的題目，Mac上著名軟件HomeBrew的作者曾經在面試Google的時候被問到了，還沒做出來，因此最后被拒。。。。于是他在個人推特上抱怨到:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

最后大家的關注點就慢慢從作者被拒本身轉移到了題目上了。。。那我們看看這道題到底有多難。

翻轉前

翻轉后

看起來好像很麻煩的樣子，每個子樹本身都被翻轉一遍。但是我們使用分治的思維，假如說我們有個函數，專門翻轉二叉樹的。假如我們把B子樹翻轉好，再把C子樹翻轉好，那么我們要做的豈不就是簡單的把A節點的左賦給C(原來是B)，再把A節點的右賦給B(原來是C)。這個問題是不是就解決了？

對于B和C我們可以用同樣的分治思維去遞歸解決。用一段代碼來描述一下

public TreeNode reverseBinaryTree(TreeNode root){
? ?//先處理base case，當root ==null 時，什么都不需要做,返回空指針
? ?if(root == null){
? ? ? ?return null;
? ?}
? ?else{
? ? ? ?//把左子樹翻轉
? ? ? ?TreeNode left = reverseBinaryTree(root.left);
? ? ? ?//把右子樹翻轉
? ? ? ?TreeNode right = reverseBinaryTree(root.right);
? ? ? ?//把左右子樹分別賦值給root節點，但是是翻轉過來的順序
? ? ? ?root.left = right;
? ? ? ?root.right = left;
? ? ? ?//返回根節點
? ? ? ?return root;
? ?}
}

根據這個例子，再加上中序打印的題目，我們應該已經可以很輕松的理解到了，對于二叉樹的題目或者算法，分而治之 和 遞歸 的核心思想了，就是把左右子樹分開處理，最后在把結果合并(把處理好的左右子樹對應根節點進行處理)。

那么接下來我們來一個復雜一點點的題目

2. 把二叉樹鋪平

這個題目我們需要把一個二叉樹變成一個類似于鏈表的結構，所有的子節點都移到右節點去，看圖為例。

轉變之后

從圖中我們可以看出來，把二叉樹鋪平的這個過程，是先把左子樹鋪平，鏈接到根節點的右節點上面，再把右子樹鋪平,鏈接到已經鋪平的左子樹的最后一個節點上。最后返回根節點。那么我們從一個宏觀的角度來說，需要做的就是先把左右子樹鋪平。

假設我們有一個方法叫flatten()，它會把一個二叉樹鋪平最后返回根節點

public TreeNode flatten(TreeNode root){ ? ?
}

那么從宏觀的角度，我們對鋪平這個操作，已經做完了！！！接下來就是第二步，還是以一個動畫來闡述這個過程。

最終代碼如下，附上注釋

public TreeNode flatten(TreeNode root){ ?
? ?//base case
? ?if(root == null){
? ? ? ?return null;
? ?}
? ?else{
? ? ? ?//用遞歸的思想，把左右先鋪平
? ? ? ?TreeNode left = flatten(root.left);
? ? ? ?TreeNode right = flatten(root.right);
? ? ? ?//把左指針和右指針先指向空。
? ? ? ?root.left = null;
? ? ? ?root.right = null;
? ? ? ?//假如左子樹生成的鏈表為空，那么忽略它，把右子樹生成的鏈表指向根節點的右指針
? ? ? ?if(left == null){
? ? ? ? ? ?root.right = right;
? ? ? ? ? ?return root;
? ? ? ?}
? ? ? ?//如果左子樹生成鏈表不為空，那么用while循環獲取最后一個節點，并且它的右指針要指向右子樹生成的鏈表的頭節點
? ? ? ?root.right = left;
? ? ? ?TreeNode lastLeft = left;
? ? ? ?while(lastLeft != null && lastLeft.right != null){
? ? ? ? ? ?lastLeft = lastLeft.right;
? ? ? ?}
? ? ? ?lastLeft.right = right;
? ? ? ?return root;
? ?}
}

至此，我們已經做完了這道題了，希望大家最后能好好理解我們所謂的分而治之的思想和二叉樹中對左右子樹遞歸的處理。大部分的二叉樹算法題也就是圍繞著這個思想為中心，只要從宏觀上能把對左右子樹處理的邏輯想清楚，那么就不難解決了。

3. 安卓開發中遇到的樹形結構？

那么對于安卓開發中，我們會不會遇到類似的問題呢？或者說安卓開發中會遇到樹形結構的算法么？

答案是肯定有！

我們都知道在安卓系統里面，每個ViewGroup里面又會包含多個或者零個View,每一個View 或者 ViewGroup 都有一個整型的Id，那么每次我們在使用ViewGroup的findViewById(int id)的時候，我們是以什么方式來查找并返回在當前ViewGroup下面，我們要查找的View呢？

這個也是我非常喜歡對來我司應聘的求職者的問題，不過很遺憾，目前為止能完完整整寫出來的就一個。。。。(再次可見東南亞開發者的水平，不忍吐槽)

那么題目來了

請完成以下方法

//返回一個在vg下面的一個View，id為方法的第二個參數
public static View find(ViewGroup vg, int id){
}

可以使用的方法有:

• View -> getId() 返回一個int 的 id

• ViewGroup -> getChildCount() 返回一個int的孩子數量

• ViewGroup -> getChildAt(int index) 返回一個孩子，返回值為View。

這個題目就可以說非常經典了，以往的樹形結構的題目，我們都是做一個二叉樹的處理，除了左就是右，但是這里我們每個ViewGroup都可能有多個孩子，每個孩子既可能是ViewGroup，也可能只是View(ViewGroup是View的子類，這里是一個知識點！)

我這里就不做過多的解釋了，直接貼代碼，而且安卓系統本身也是用這種方式進行View的查找的。

//返回一個在vg下面的一個View，id為方法的第二個參數
public static View find(ViewGroup vg, int id){
? ?if(vg == null) return null;
? ?int size = vg.getChildCount();
? ?//循環遍歷所有孩子
? ?for(int i = 0 ; i< size ;i++){
? ? ? ?View v = vg.getChildAt(i);
? ? ? ?//如果當前孩子的id相同，那么返回
? ? ? ?if(v.getId == id) return v;
? ? ? ?//如果當前孩子id不同，但是是一個ViewGroup，那么我們遞歸往下找
? ? ? ?if(v instance of ViewGroup){
? ? ? ? ? ?//遞歸
? ? ? ? ? ?View temp = find((ViewGroup)v,id);
? ? ? ? ? ?//如果找到了，就返回temp，如果沒有找到，繼續當前的for循環
? ? ? ? ? ?if(temp != null){
? ? ? ? ? ? ? ?return temp;
? ? ? ? ? ?}
? ? ? ?}
? ?}
? ?//到最后還沒用找到，代表該ViewGroup vg 并不包含一個有該id的孩子，返回空
? ?return null;
}

“

?三、二叉樹的層序處理(廣度優先)

說到廣度優先，大部分同學可能會想到圖，不過畢竟樹結構本身就是一種特殊的圖。所以一般說樹，尤其是二叉樹的廣度優先我們指的一般是層序遍歷。

比如說樹

層序打印的結果就是A->B->C->D->D->E->F->G

對于層序遍歷的相關算法，真理只有一個！

就是用隊列(Queue)！

道理很簡單，每次遍歷當前節點的時候，把該節點從隊列拿出來，并且把它的子節點全部加入到隊列中。over~

上一個簡單的打印代碼

public void printTree(TreeNode root){
? ?if(root == null){
? ? ? ?return;
? ?}
? ?Queue queue = new LinkedList();
? ?queue.add(root);
? ?while(!queue.isEmpty()){
? ? ? ?TreeNode current = queue.poll();
? ? ? ?System.out.println(current.toString());
? ? ? ?if(current.left != null){
? ? ? ? ? ?queue.add(current.left);
? ? ? ?}
? ? ? ?if(current.right != null){
? ? ? ? ? ?queue.add(current.right);
? ? ? ?}
? ?}
}

這段代碼很簡單，利用隊列先進先出的性質，我們可以一層層的打印二叉樹的節點們。

所以對于二叉樹的層序遍歷來說，一般都會使用隊列，這都是套路。因此，二叉樹的層序遍歷相對來說比較簡單，大家下次見到二叉樹的層序遍歷相關的面試題，先大膽的和面試官說出你打算使用隊列，肯定沒錯！

最后對于層序遍歷來說我們再來一個比較具有代表性的題目！

1. 鏈接二叉樹的Next節點

這個題目要求大家在擁有一個二叉樹節點的左右節點指針之余，還要幫它找到它的next指針指向的節點。

大概是這樣：

在上面這個圖中，紅色的箭頭代表next指針的指向

邏輯很簡單，每一個的節點的next指向同一層中的下一個節點，不過如果該節點是當前層的最后一個節點的話，不設置next，或者說next為空。

其實這個題目就是典型的層序遍歷，使用隊列就可以輕松解決，每次poll出來一個節點，判斷是不是當前層的最后一個，如果不是，把其next設置成queue中的下一個節點就ok了。至于怎么判斷當前節點是哪一層呢？我們有個小技巧，使用當前queue的size做for循環，且看代碼

public void nextSibiling(TreeNode node){
? ?if(node == null){
? ? ? ?return;
? ?}
? ?Queue queue = new LinkedList();
? ?queue.add(node);
? ?//這個level沒有實際用處，但是可以告訴大家怎么判斷當前node是第幾層。
? ?int level = 0;
? ?while(!queue.isEmpty()){
? ? ? ?int size = queue.size();
? ? ? ?//用這個for循環，可以保證for循環里面對queue不管加多少個子節點，我只處理當前層里面的節點
? ? ? ?for(int i = 0;i<size;i++){
? ? ? ? ? ? ? ?//把當前第一個節點拿出來
? ? ? ? ? ? ? ?TreeNode current = queue.poll();
? ? ? ? ? ? ? ?//把子節點加到queue里面
? ? ? ? ? ? ? ?if(current.left != null){
? ? ? ? ? ? ? ? ? ?queue.add(current.left);
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?if(current.right != null){
? ? ? ? ? ? ? ? ? ?queue.add(current.right);
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?if(i != size -1){
? ? ? ? ? ? ? ? ? ?//peek只是獲取當前隊列中第一個節點，但是并不把它從隊列中拿出來
? ? ? ? ? ? ? ? ? ?current.next = queue.peek();
? ? ? ? ? ? ? ?}
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?level++;
? ?}
}

“

?四、總結

二叉樹的知識點我就大概講這些，下次的文章我會接著詳細的講深度優先和廣度優先的算法。深度優先是一個非常非常寬泛而且難以完全掌握的知識點，我會用詳細的篇幅來覆蓋所有的深度優先的基本題型，包括對樹，圖的深度優先搜索，集合的回朔等等。

如果您覺得不錯，請別忘了轉發、分享、點贊讓更多的人去學習， 您的舉手之勞，就是對小樂最好的支持，非常感謝！

如何您想進技術群和大牛們交流，關注公眾號在后臺回復 “加群”，或者 “學習”?即可

來自：qing的世界

鏈接：https://www.jianshu.com/p/6f179f37ad79

著作權歸作者所有。本文已獲得授權。歡迎大家來投稿。

每日英文

Sometimes?we?want?things?to?be?different,we?think?maybe?if?we?pretend?that?they?are,fool?people,that’s?enough,but?it?never?is.?

有時候我們希望事情有所改變，覺得如果我們假裝那是我們想要的，欺騙別人?，那樣就行了，但事實上不是。

樂樂有話說

時間是一把戳穿虛偽的刀，它驗證了謊言，揭露了現實，淡化了承諾。

總結

以上是生活随笔為你收集整理的Android面试题算法之二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。