第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

1. 前言

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

2. 二叉樹視圖

2.1 二叉樹右視圖

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

題目解析：

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

首先給出二叉樹右視圖的定義：從二叉樹的右邊看到的第一個(gè)節(jié)點(diǎn)，即是當(dāng)前層數(shù)的結(jié)果節(jié)點(diǎn)，把所有的結(jié)果節(jié)點(diǎn)添加到集合，即是結(jié)果集合。

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

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

我們使用雙向隊(duì)列作為數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)層次遍歷的結(jié)果，我們要解決兩個(gè)問題，一是如何實(shí)現(xiàn)層次遍歷，二是如何判斷是否是每層的最右邊的節(jié)點(diǎn)。

（1）初始條件：首先把根節(jié)點(diǎn)放入雙向隊(duì)列尾部；
（2）最右判斷：每次首先得到雙向隊(duì)列當(dāng)前的長(zhǎng)度 size，這是一個(gè)固定值，對(duì)于第一層來說，因?yàn)橹挥幸粋€(gè)根節(jié)點(diǎn)，所以 size-1 的位置就是最右邊的節(jié)點(diǎn)；
（3）循環(huán)處理：以size作為循環(huán)次數(shù)，從雙向隊(duì)列頭部開始，不斷彈出節(jié)點(diǎn)，將每個(gè)節(jié)點(diǎn)的非空左右子樹加入雙向隊(duì)列尾部。當(dāng)遍歷到 size-1 的位置時(shí)，就是當(dāng)前層數(shù)的最右節(jié)點(diǎn)。一直循環(huán)，直到雙向隊(duì)列為空，即處理完所有的二叉樹節(jié)點(diǎn)。

在 Java中 使用 ArrayDeque 數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)雙向隊(duì)列，下面給出 Java 算法的源碼以及注解，示例：

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

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

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

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

（1）二叉樹右視圖：每次獲取當(dāng)前層雙向隊(duì)列的最后一個(gè)節(jié)點(diǎn)；
（2）二叉樹左視圖：每次獲取當(dāng)前層雙向隊(duì)列的第一個(gè)節(jié)點(diǎn)；
（3）二叉樹層次遍歷：對(duì)于每遍歷一次 size ，結(jié)果添加到一個(gè)單獨(dú)的列表。

3. 小結(jié)

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