1、深度優(yōu)先和廣度優(yōu)先的區(qū)別
?1） 二叉樹的深度優(yōu)先遍歷的非遞歸的通用做法是采用棧，廣度優(yōu)先遍歷的非遞歸的通用做法是采用隊(duì)列。
?2） 深度優(yōu)先遍歷：對(duì)每一個(gè)可能的分支路徑深入到不能再深入為止，而且每個(gè)結(jié)點(diǎn)只能訪問(wèn)一次。要特別注意的是，二叉樹的深度優(yōu)先遍歷比較特殊，可以細(xì)分為先序遍歷、中序遍歷、后序遍歷。具體說(shuō)明如下：
先序遍歷：對(duì)任一子樹，先訪問(wèn)根，然后遍歷其左子樹，最后遍歷其右子樹。
中序遍歷：對(duì)任一子樹，先遍歷其左子樹，然后訪問(wèn)根，最后遍歷其右子樹。
后序遍歷：對(duì)任一子樹，先遍歷其左子樹，然后遍歷其右子樹，最后訪問(wèn)根。
廣度優(yōu)先遍歷：又叫層次遍歷，從上往下對(duì)每一層依次訪問(wèn)，在每一層中，從左往右（也可以從右往左）訪問(wèn)結(jié)點(diǎn)，訪問(wèn)完一層就進(jìn)入下一層，直到?jīng)]有結(jié)點(diǎn)可以訪問(wèn)為止。
?3）深度優(yōu)先搜素算法：不全部保留結(jié)點(diǎn)，占用空間少；有回溯操作(即有入棧、出棧操作)，運(yùn)行速度慢。
廣度優(yōu)先搜索算法：保留全部結(jié)點(diǎn)，占用空間大； 無(wú)回溯操作(即無(wú)入棧、出棧操作)，運(yùn)行速度快。
2、數(shù)組和鏈表的區(qū)別
1） 數(shù)組
是將元素在內(nèi)存中連續(xù)存放,由于每個(gè)元素占用內(nèi)存相同,可以通過(guò)下標(biāo)迅速訪問(wèn)數(shù)組中任何元素。
數(shù)組必須事先定義固定的長(zhǎng)度（元素個(gè)數(shù)），不能適應(yīng)數(shù)據(jù)動(dòng)態(tài)地增減的情況。當(dāng)數(shù)據(jù)增加時(shí)，可能超出原先定義的元素個(gè)數(shù)；當(dāng)數(shù)據(jù)減少時(shí)，造成內(nèi)存浪費(fèi)；數(shù)組可以根據(jù)下標(biāo)直接存取。
數(shù)組的存儲(chǔ)區(qū)間是連續(xù)的，從棧中分配空間，占用內(nèi)存比較大；插入數(shù)據(jù)和刪除數(shù)據(jù)效率低。
?插入數(shù)據(jù)時(shí)，待插入位置的元素和他后面的所有元素都需要向后搬移
?刪除數(shù)據(jù)時(shí)，待刪除位置后面的所有元素都需要向前搬移。
查找速度快，時(shí)間復(fù)雜度是o(1)； 從頭部刪除、從頭部插入的效率低，時(shí)間復(fù)雜度是o(n)。
偽數(shù)組和數(shù)組的區(qū)別
偽數(shù)組的特點(diǎn)：a、具有l(wèi)ength屬性；b、按索引方式存儲(chǔ)數(shù)組；c、不具有數(shù)組的方法。
常見(jiàn)的偽數(shù)組：a、函數(shù)內(nèi)部的arguments；b、DOM 對(duì)象列表（比如通過(guò) document.getElementsByTags 得到的列表）；c、Query 對(duì)象（比如 $("div") ）。
偽數(shù)組轉(zhuǎn)成數(shù)組的方法：a、Array.prototype.slice.call(偽數(shù)組名)；b、Array.from()；c、 ...運(yùn)算符如： let newArr = [...偽數(shù)組名];。
2）鏈表
是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。
鏈表動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配，鏈表從堆中分配空間，空間是分散的，不需要連續(xù)，空間不需要提前指定大小，可以適應(yīng)數(shù)據(jù)動(dòng)態(tài)地增減的情況，且可以方便地插入、刪除數(shù)據(jù)項(xiàng)。（數(shù)組中插入、刪除數(shù)據(jù)項(xiàng)時(shí)，需要移動(dòng)其它數(shù)據(jù)項(xiàng)，非常繁瑣）鏈表必須根據(jù)next指針找到下一個(gè)元素。
查找速度慢，時(shí)間復(fù)雜度是o(n)；任意位置插入元素和刪除元素時(shí)間效率較高，時(shí)間復(fù)雜度是o(1)。
比較
數(shù)組的底層是ArrayList,鏈表的底層是Hashmap。
3、哈希
哈希是通過(guò)對(duì)數(shù)據(jù)進(jìn)行再壓縮，提高效率的一種解決方法。但由于通過(guò)哈希函數(shù)產(chǎn)生的哈希值是有限的，而數(shù)據(jù)可能比較多，導(dǎo)致經(jīng)過(guò)哈希函數(shù)處理后仍然有不同的數(shù)據(jù)對(duì)應(yīng)相同的值。這時(shí)候就產(chǎn)生了哈希沖突。
1）哈希沖突的影響因素
裝填因子（裝填因子=數(shù)據(jù)總數(shù) / 哈希表長(zhǎng)）、哈希函數(shù)、處理沖突的方法。
2）哈希沖突的四種方法
a、開放地址方法
線性探測(cè)：按順序決定值時(shí)，如果某數(shù)據(jù)的值已經(jīng)存在，則在原來(lái)值的基礎(chǔ)上往后加一個(gè)單位，直至不發(fā)生哈希沖突。
再平方探測(cè)：按順序決定值時(shí)，如果某數(shù)據(jù)的值已經(jīng)存在，則在原來(lái)值的基礎(chǔ)上先加1的平方個(gè)單位，若仍然存在則減1的平方個(gè)單位。隨之是2的平方，3的平方等等。直至不發(fā)生哈希沖突。
偽隨機(jī)探測(cè)：按順序決定值時(shí)，如果某數(shù)據(jù)已經(jīng)存在，通過(guò)隨機(jī)函數(shù)隨機(jī)生成一個(gè)數(shù)，在原來(lái)值的基礎(chǔ)上加上隨機(jī)數(shù)，直至不發(fā)生哈希沖突。
b、拉鏈法（HashMap的哈希沖突解決方法）
對(duì)于相同的值，使用鏈表進(jìn)行連接。使用數(shù)組存儲(chǔ)每一個(gè)鏈表。
優(yōu)點(diǎn)：拉鏈法處理沖突簡(jiǎn)單，且無(wú)堆積現(xiàn)象，即非同義詞決不會(huì)發(fā)生沖突，因此平均查找長(zhǎng)度較短；
由于拉鏈法中各鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的，故它更適合于造表前無(wú)法確定表長(zhǎng)的情況；
開放定址法為減少?zèng)_突，要求裝填因子α較小，故當(dāng)結(jié)點(diǎn)規(guī)模較大時(shí)會(huì)浪費(fèi)很多空間。而拉鏈法中可取α≥1，且結(jié)點(diǎn)較大時(shí)，拉鏈法中增加的指針域可忽略不計(jì)，因此節(jié)省空間；
在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)。只要簡(jiǎn)單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可。
缺點(diǎn)：指針占用較大空間時(shí)，會(huì)造成空間浪費(fèi)，若空間用于增大散列表規(guī)模進(jìn)而提高開放地址法的效率。
c、再哈希法
對(duì)于沖突的哈希值再次進(jìn)行哈希函數(shù)去散列處理，直至沒(méi)有哈希沖突。
4、排序算法
在平均情況下，快速排序最快；
在最好情況下，插入排序和起泡排序最快；
在最壞情況下，堆排序和歸并排序最快。
5、Map 和 Object 的區(qū)別
1）鍵值key不同
Object 的 key 必須是簡(jiǎn)單數(shù)據(jù)類型（整數(shù)，字符串或者是 symbol）；而在Map的鍵可以是任意值，包括函數(shù)、對(duì)象、基本類型。
2）元素的順序
Map 中的鍵值是有序的，而添加到對(duì)象中的鍵則不是。因此，當(dāng)對(duì)它進(jìn)行遍歷時(shí)，Map 對(duì)象是按插入的順序返回鍵值。
3）操作方法
a、新建：Object 支持以下幾種方法；Map 僅支持一種構(gòu)建方法：new Map()；
b、新增數(shù)據(jù)（重復(fù)則覆蓋）：Map 可以使用 set(key, val) 操作；Object 新增一個(gè)屬性可以使用：obj['key']=value或obj.key=value。
c、數(shù)據(jù)訪問(wèn)：Map 想要訪問(wèn)元素，可以使用 Map 本身的原生方法get (key) ；Object 可以通過(guò).和[ ]來(lái)訪問(wèn)。
d、刪除數(shù)據(jù)：Map 有原生的 delete 方法來(lái)刪除元素；全部刪除map.clear();
Object 中沒(méi)有原生的刪除方法，可以使用：deleteobj.id;或obj.id=undefined。
e、獲取size：Map 自身有 size 屬性，可以自己維持 size 的變化。Object 則需要借助Object.keys()來(lái)計(jì)算：Object.keys(obj).length。
f、可訪問(wèn)性：判斷某個(gè)元素是否在 Map 中可以使用has (key)；判斷某個(gè)元素是不是在 Object 中可以用obj.id===undefined;// 或者'id'inobj;
另外Object 可以使用Object.prototype.hasOwnProperty()來(lái)判斷某個(gè)key是否是這個(gè)對(duì)象本身的屬性，從原型鏈繼承的屬性不包括在內(nèi)。
g、Iterating 迭代：Map 自身支持迭代，Object 不支持。Map可直接進(jìn)行迭代，而Object的迭代需要先獲取它的鍵數(shù)組，然后再進(jìn)行迭代。
何時(shí)使用 Map ，何時(shí)使用 Object？
a、當(dāng)所要存儲(chǔ)的是簡(jiǎn)單數(shù)據(jù)類型，并且 key 都為字符串或者整數(shù)或者 Symbol 的時(shí)候，優(yōu)先使用 Object ，因?yàn)镺bject可以使用 字符變量 的方式創(chuàng)建，更加高效；
Map 在存儲(chǔ)大量元素的時(shí)候性能表現(xiàn)更好，特別是在代碼執(zhí)行時(shí)不能確定 key 的類型的情況。
b、在涉及頻繁增刪鍵值對(duì)的場(chǎng)景下應(yīng)該使用 Map。
c、JSON 直接支持 Object，但不支持 Map。
6、二叉搜索樹
二叉查找樹（Binary Search Tree），（又：二叉搜索樹，二叉排序樹）它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值； 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； 它的左、右子樹也分別為二叉排序樹。
刪除節(jié)點(diǎn)：
情況1：刪除的當(dāng)前節(jié)點(diǎn)無(wú)左右孩子節(jié)點(diǎn)，那么就直接將當(dāng)前要?jiǎng)h除的節(jié)點(diǎn)設(shè)置為null即可。
情況2：刪除的當(dāng)前節(jié)點(diǎn)無(wú)左孩子節(jié)點(diǎn)，有右孩子節(jié)點(diǎn)，那么就將當(dāng)前要?jiǎng)h除的節(jié)點(diǎn)設(shè)置為右孩子節(jié)點(diǎn)即可。
情況3：刪除的當(dāng)前節(jié)點(diǎn)無(wú)右孩子節(jié)點(diǎn)，有左孩子節(jié)點(diǎn)，那么就將當(dāng)前要?jiǎng)h除的節(jié)點(diǎn)設(shè)置為左孩子節(jié)點(diǎn)即可。
情況4：刪除的當(dāng)前節(jié)點(diǎn)有右孩子節(jié)點(diǎn)也有左孩子節(jié)點(diǎn)，那么就選出右孩子樹中最小的點(diǎn)，設(shè)置為當(dāng)前要?jiǎng)h除的節(jié)點(diǎn)即可。這種方式既可以保證二叉排序樹的性質(zhì)，由于右孩子樹中最小的點(diǎn)，無(wú)左孩子節(jié)點(diǎn)（如果有左孩子節(jié)點(diǎn)，那么就不符合二叉樹性質(zhì)了）。
