亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

1. 前言

除了可以直接使用遞歸處理的二叉樹問題，二叉樹中還有一些典型的算法問題，需要和其他的數據結構配合解決，例如使用堆、棧以及隊列數據結構配合查找的過程，可以避免使用遞歸算法。

2. 二叉樹視圖

2.1 二叉樹右視圖

面試官提問：給定一顆二叉樹，求出從二叉樹右邊看到的所有節點結果集合。

題目解析：

求解二叉樹右視圖問題是來源于算法網站LeetCode的經典題目，題目鏈接：https://leetcode.com/problems/binary-tree-right-side-view/。

首先給出二叉樹右視圖的定義：從二叉樹的右邊看到的第一個節點，即是當前層數的結果節點，把所有的結果節點添加到集合，即是結果集合。

舉例來說，對于上圖中的二叉樹結果，其右視圖的結果集是[3,20,8]。

根據題意，最明顯的方法是層次遍歷二叉樹，也就是BFS廣度優先搜索算法，按照這個思路。

我們使用雙向隊列作為數據結構存儲層次遍歷的結果，我們要解決兩個問題，一是如何實現層次遍歷，二是如何判斷是否是每層的最右邊的節點。

（1）初始條件：首先把根節點放入雙向隊列尾部；
（2）最右判斷：每次首先得到雙向隊列當前的長度 size，這是一個固定值，對于第一層來說，因為只有一個根節點，所以 size-1 的位置就是最右邊的節點；
（3）循環處理：以size作為循環次數，從雙向隊列頭部開始，不斷彈出節點，將每個節點的非空左右子樹加入雙向隊列尾部。當遍歷到 size-1 的位置時，就是當前層數的最右節點。一直循環，直到雙向隊列為空，即處理完所有的二叉樹節點。

在 Java中 使用 ArrayDeque 數據結構實現雙向隊列，下面給出 Java 算法的源碼以及注解，示例：

public List<Integer> rightSideView(TreeNode root) {
	Queue<TreeNode> q= new ArrayDeque<>();
    List<Integer> res = new ArrayList<>();
	//如果是空節點，直接返回空結果集
    if(root == null) 
    	return res;
    //將根節點添加到隊列
    q.offer(root);
    while(!q.isEmpty()){
        int size = q.size();
        for(int i = 0; i< size; i++){
        	//從雙向隊列頭部彈出第一個節點
            TreeNode node = q.poll();
            //如果是當前層數的最后一個節點，就是需要的右視圖節點
            if(i == size-1) 
          		res.add(node.val);
          	//彈出節點的有效左節點加入隊列
            if(node.left != null) 
            	q.offer(node.left);
            //彈出節點的有效右節點加入隊列
            if(node.right != null) 
            	q.offer(node.right);
        }
    }
    //返回結果集
    return res;
}

當然除了 BFS 算法外，本題目也可以使用 DFS 算法，即通過前序遍歷獲取需要的最右節點，這里不再贅述。

2.2 二叉樹左視圖、二叉樹層次遍歷

求解二叉樹左視圖、二叉樹右視圖、二叉樹層次遍歷問題，都可以使用雙向隊列求解。

（1）二叉樹右視圖：每次獲取當前層雙向隊列的最后一個節點；
（2）二叉樹左視圖：每次獲取當前層雙向隊列的第一個節點；
（3）二叉樹層次遍歷：對于每遍歷一次 size ，結果添加到一個單獨的列表。

3. 小結

候選人在學習算法問題時，需要注意舉一反三，目前算法網站的面試題題庫已經接近 2000 題，如果企圖通過刷遍題庫的方式提高算法能力，是非常消耗精力的。所以要做到精簡問題和總結算法套路，例如本章中介紹的二叉樹和雙向隊列配合使用，實現廣度優先搜索，就是一個非常典型的算法模板，可以多加熟悉。