介紹
- 二叉樹的結(jié)構(gòu)
- 二叉樹城捎椋考的原因有如下幾點(diǎn)
1碉怔、它可以結(jié)合鏈表、棧禁添、隊(duì)列和字符串等數(shù)據(jù)結(jié)構(gòu)出題
2撮胧、需要熟練掌握?qǐng)D的BFS，DFS遍歷
3上荡、需掌握遞歸函數(shù)的使用趴樱，并根據(jù)題義自己設(shè)定遞歸過程
4、工程上二叉樹比較常用 - 面試中酪捡，默認(rèn)二叉樹只有數(shù)據(jù)項(xiàng)叁征、左孩子指針、右孩子指針逛薇。
- 工程上常常會(huì)用到節(jié)點(diǎn)包含指向其父節(jié)點(diǎn)的二叉樹捺疼。
相關(guān)概念
- 二叉樹的子樹：以二叉樹中任意節(jié)點(diǎn)為根的子樹
- 平衡二叉樹(AVL)：二叉樹中任意一顆子樹的左右子樹的深度差小于等于1（平衡二叉樹是在構(gòu)造二叉排序樹的過程中，每當(dāng)插入一個(gè)新結(jié)點(diǎn)時(shí)永罚，首先檢查是否因插入新結(jié)點(diǎn)而破壞了二叉排序樹的平衡性啤呼，若是，則找出其中的最小不平衡子樹呢袱，在保持二叉排序樹特性的前提下官扣，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)羞福，使之成為新的平衡子樹惕蹄，空樹是平衡二叉樹，平衡二叉樹首先是二叉排序樹）
- 搜索二叉樹：二叉樹中治专，每顆子樹的左子樹的所有節(jié)點(diǎn)值都小于根節(jié)點(diǎn)卖陵，右子樹的所有節(jié)點(diǎn)值都大于根節(jié)點(diǎn)
- 紅黑樹、平衡搜索二叉樹：這兩種樹都是搜索二叉樹的不同實(shí)現(xiàn)张峰，它們都提高了搜索二叉樹的搜索效率泪蔫，同時(shí)減少了調(diào)整為搜索二叉樹的代價(jià)
- 滿二叉樹：除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉結(jié)點(diǎn)都處在最底層的二叉樹,設(shè)二叉樹的高度為L撩荣，節(jié)點(diǎn)樹為N老速，則滿足等式N = 2L - 1的二叉樹為滿二叉樹额湘，滿二叉樹的高度可以根據(jù)L = log(N + 1)計(jì)算
- 完全二叉樹(堆結(jié)構(gòu)就是一種完全二叉樹)：非滿二叉樹的完全二叉樹的最后一層都集中在樹的左邊
- 后繼節(jié)點(diǎn)：二叉樹中序遍歷中，該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
- 前驅(qū)節(jié)點(diǎn)：二叉樹中序遍歷中衍腥，該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
- 度：指的是一個(gè)節(jié)點(diǎn)擁有子節(jié)點(diǎn)的個(gè)數(shù)婆咸。如二叉樹的節(jié)點(diǎn)的最大度為2侵续。
- 深度：數(shù)的層數(shù)状蜗，根節(jié)點(diǎn)為第一層宏邮，依次類推。
- 葉子節(jié)點(diǎn)：度為0的節(jié)點(diǎn)，即沒有子節(jié)點(diǎn)的節(jié)點(diǎn)定欧。
- 哈夫曼樹：帶權(quán)路徑長度達(dá)到最小的二叉樹，也叫做最優(yōu)二叉樹爷辱。不關(guān)心樹的結(jié)構(gòu)，只要求帶權(quán)值的路徑達(dá)到最小值弟断，哈夫曼樹可能是完全二叉樹也可能是滿二叉樹。
二叉樹的性質(zhì)
- 在二叉樹中，第i層的結(jié)點(diǎn)總數(shù)不超過2^(i-1)排霉；
- 深度為h的二叉樹最多有2^h-1個(gè)結(jié)點(diǎn)(h>=1)，最少有h個(gè)結(jié)點(diǎn)；
- 對(duì)于任意一棵二叉樹浪谴，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，則N0=N2+1智蝠；
- 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為int（log2n）+1
- 有N個(gè)結(jié)點(diǎn)的完全二叉樹各結(jié)點(diǎn)如果用順序方式存儲(chǔ)，則結(jié)點(diǎn)之間有如下關(guān)系：若I為結(jié)點(diǎn)編號(hào)則 如果I<>1叫挟，則其父結(jié)點(diǎn)的編號(hào)為I/2署驻；如果2I <= N，則其左兒子（即左子樹的根結(jié)點(diǎn)）的編號(hào)為2I旺上；若2I>N瓶蚂，則無左兒子；如果2I+1<=N宣吱，則其右兒子的結(jié)點(diǎn)編號(hào)為2I+1窃这；若2I+1>N，則無右兒子（根節(jié)點(diǎn)的編號(hào)為1）征候。
- (6)給定N個(gè)節(jié)點(diǎn)杭攻，能構(gòu)成h(N)種不同的二叉樹。
- h(N)為卡特蘭數(shù)的第N項(xiàng)疤坝。h(n)=C(n,2*n)/(n+1)兆解。
經(jīng)典題
-
用遞歸和非遞歸的方式實(shí)現(xiàn)二叉樹的先序、中序跑揉、后序遍歷
- ①非遞歸方式實(shí)現(xiàn)先序遍歷
具體過程：
1锅睛、首先申請(qǐng)一個(gè)新的棧，記為stack历谍。
2现拒、然后將頭節(jié)點(diǎn)head壓入stack中。
3望侈、每次從stack中彈出棧頂節(jié)點(diǎn)印蔬，記為cur，然后打印cur節(jié)點(diǎn)的值甜无。如果cur右孩子不為空的話扛点，將cur的右孩子先壓入stack中哥遮。最后如果cur的左孩子不為空的話，將cur的左孩子壓入stack中陵究。
4眠饮、不斷重復(fù)步驟3，直到stack為空铜邮，全部過程結(jié)束仪召。 - ②非遞歸方法實(shí)現(xiàn)中序遍歷
具體過程：
1、申請(qǐng)一個(gè)新的棧松蒜，記為stack扔茅，申請(qǐng)一個(gè)變量cur，初始時(shí)令cur等于頭節(jié)點(diǎn)秸苗。
2召娜、先把cur節(jié)點(diǎn)壓入棧中，對(duì)以cur節(jié)點(diǎn)為頭的整棵子樹來說惊楼，依次把整棵樹的左邊界壓入棧中玖瘸，即不斷令cur=cur.left，然后重復(fù)步驟2檀咙。
3雅倒、不斷重復(fù)步驟2，直到發(fā)現(xiàn)cur為空弧可，此時(shí)從stack中彈出一個(gè)節(jié)點(diǎn)蔑匣，記為node。打印node的值棕诵，并讓cur=node.right裁良，然后繼續(xù)重復(fù)步驟2。
4年鸳、當(dāng)stack為空并且cur為空時(shí)趴久，整個(gè)過程結(jié)束。 - ③非遞歸方法實(shí)現(xiàn)后序遍歷方法一：使用兩個(gè)棧實(shí)現(xiàn)
具體過程如下：
1搔确、申請(qǐng)一個(gè)棧彼棍，記為s1，然后將頭節(jié)點(diǎn)壓入s1中膳算。
2座硕、從s1中彈出的節(jié)點(diǎn)記為cur，然后先把cur的左孩子壓入s1中涕蜂，然后把cur1的右孩子壓入s1中华匾。
3、在整個(gè)過程中机隙，每一個(gè)從s1中彈出的節(jié)點(diǎn)都放進(jìn)第二個(gè)棧s2中蜘拉。
4萨西、不斷重復(fù)步驟2和步驟3，直到51為空旭旭，過程停止谎脯。
5、從s2中依次彈出節(jié)點(diǎn)并打印持寄，打印的順序就是后序遍歷的順序了源梭。 - ④非遞歸方法實(shí)現(xiàn)后序遍歷方法二：使用一個(gè)棧實(shí)現(xiàn)
具體過程如下：
1、申請(qǐng)一個(gè)棧稍味，記為stack废麻，將頭節(jié)點(diǎn)壓入stack，同時(shí)設(shè)置兩個(gè)變量h和c模庐。在整個(gè)流程中烛愧，h代表最近一次彈出并打印的節(jié)點(diǎn)，c代表當(dāng)前stack的棧頂節(jié)點(diǎn)掂碱，初始時(shí)令h為頭節(jié)點(diǎn)屑彻，c為null。
2顶吮、每次令c等于當(dāng)前stack的棧頂節(jié)點(diǎn)，但是不從stack中彈出節(jié)點(diǎn)粪薛，此時(shí)分以下三種情況悴了。
（1）如果c的左孩子不為空，并且h不等于c的左孩子违寿，也不等于c的右孩子湃交，則把c的左孩子壓入stack中。
（2）如果情況1不成立藤巢，并且c的右孩子不為空搞莺，并且h不等于c的右孩子，則把c的右孩子壓入stack中掂咒。
（3）如果情況1和情況2都不成立才沧，那么從stack中彈出c并打印，然后令h等于c绍刮。
3温圆、一直重復(fù)步驟2，直到stack為空孩革，過程停止岁歉。 - 先序，中序和后序的遞歸算法如下：
- ①非遞歸方式實(shí)現(xiàn)先序遍歷
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class TreeToSequence:
def fore_seq(self, root, result):
if root != None:
result[0].extend([root.val])
self.fore_seq(root.left, result)
self.fore_seq(root.right, result)
def inter_seq(self, root, result):
if root != None:
self.inter_seq(root.left, result)
result[1].extend([root.val])
self.inter_seq(root.right, result)
def back_seq(self, root, result):
if root != None:
self.back_seq(root.left, result)
self.back_seq(root.right, result)
result[2].extend([root.val])
def convert(self, root):
# write code here
result = [[], [], []]
self.fore_seq(root, result)
self.inter_seq(root, result)
self.back_seq(root, result)
#以二維數(shù)組的形式返回先序膝蜈、中序和后序遍歷序列
return result
不管是遞歸方法還是非遞歸方法锅移，遍歷整棵樹的時(shí)間復(fù)雜度都是O（N）熔掺，N為二叉樹的節(jié)點(diǎn)數(shù)，額外空間復(fù)雜度為O（L）非剃，L為二叉樹的層數(shù)置逻。
判斷以head為根的樹是否為平衡二叉樹
采用后序遍歷的思想，每次遍歷某節(jié)點(diǎn)的左（右）子樹時(shí)記錄其是否為平衡二叉樹努潘，如果不是平衡二叉樹則返回False诽偷，如果是平衡二叉樹，則返回其樹高疯坤，之后比較左右子樹樹高差距是否小于等于1报慕，如果是，則以該節(jié)點(diǎn)為根的子樹為平衡二叉樹压怠，否則不是平衡二叉樹眠冈。判斷以head為根的子樹書否為搜索二叉樹
中序遍歷二叉樹的同時(shí)判斷當(dāng)前節(jié)點(diǎn)是否小于中序后繼節(jié)點(diǎn)，為了方便菌瘫，采用非遞歸方法實(shí)現(xiàn)中序遍歷判斷以head為根的二叉樹是否為完全二叉樹
從左到右按層次遍歷二叉樹的同時(shí)用排除法判斷蜗顽，具體如下：
1、如果當(dāng)前節(jié)點(diǎn)只有右孩子雨让，返回False
2雇盖、如果當(dāng)前節(jié)點(diǎn)只有左孩子，則如果后序節(jié)點(diǎn)有非葉子節(jié)點(diǎn)栖忠，則返回False
3崔挖、如果遍歷完整，沒有返回False庵寞，則返回True-
給定存在指向父節(jié)點(diǎn)的指針parent的二叉樹狸相，請(qǐng)返回給定節(jié)點(diǎn)node的后繼節(jié)點(diǎn)。
1捐川、一般解法為先根據(jù)parent找到根節(jié)點(diǎn)脓鹃，再中序遍歷，這種解法時(shí)間和空間復(fù)雜度都是O(N)
2古沥、最優(yōu)解可以做到時(shí)間復(fù)雜度為O(L)瘸右，L為node到其后繼節(jié)點(diǎn)的實(shí)際距離，時(shí)間復(fù)雜度為O(1)：- 如果node有右子樹渐白，則其后繼為其右子樹的最左節(jié)點(diǎn)
- 如果node無右子樹尊浓，但它是其父節(jié)點(diǎn)的左子樹，則其父節(jié)點(diǎn)為其后繼
- 如果node無右子樹纯衍，且是其父節(jié)點(diǎn)的右孩子栋齿，則需要向上查找，目標(biāo)為其父節(jié)點(diǎn)（包括隔代父節(jié)點(diǎn)）為其父節(jié)點(diǎn)的左子樹，則其父節(jié)點(diǎn)的父節(jié)點(diǎn)就是node的后繼（這時(shí)瓦堵，node實(shí)際上是其后繼節(jié)點(diǎn)左子樹的最右節(jié)點(diǎn)）
- 一直向上查找基协，直到空，如果沒找到菇用，則無后繼
從下往上對(duì)折紙條澜驮，會(huì)在紙條上留下折痕洽洁，對(duì)折一次留下向下折痕鹏氧，對(duì)折兩次從上往下播演，依次為向下殊鞭、向下、向上诀黍，給定對(duì)折次數(shù)N糜俗，請(qǐng)打印紙條展開后從上到下的折痕方向的序列
第一次對(duì)折會(huì)留下一條向下的折痕缩擂，后序每對(duì)折一次滤港，會(huì)在原來對(duì)折留下折痕的上下分別留下向下和向上的折痕廊蜒，句子可知，折痕情況可以形式化為滿二叉樹的節(jié)點(diǎn)溅漾，節(jié)點(diǎn)值為折痕的方向山叮，按右-中-左順序遍歷即可得到紙條從上到下的折痕序列，N為樹高給定搜索二叉樹添履，頭節(jié)點(diǎn)為head屁倔，其中有兩個(gè)節(jié)點(diǎn)位置發(fā)生了調(diào)換，請(qǐng)打印被調(diào)換位置的節(jié)點(diǎn)
中序遍歷二叉樹暮胧，則被調(diào)換節(jié)點(diǎn)出現(xiàn)在序列中出現(xiàn)降序的位置汰现，且為第一次降序位置的較大節(jié)點(diǎn)和最后一次（可能只有一次降序）降序位置的較小節(jié)點(diǎn)。-
給定二叉樹叔壤，頭節(jié)點(diǎn)為head，請(qǐng)返回所有節(jié)點(diǎn)間的最大距離
某子樹頭節(jié)點(diǎn)為A口叙，出現(xiàn)距離最大的三種情況：- 記左子樹中所有節(jié)點(diǎn)和節(jié)點(diǎn)A的距離最大值為Lmax炼绘，記右子樹中所有節(jié)點(diǎn)和節(jié)點(diǎn)A的距離最大值為Rmax，max1 = Lmax + 1 + Rmax妄田。
- 左子樹中所有非頭結(jié)點(diǎn)之間的最大距離：max2
- 右子樹中所有非頭結(jié)點(diǎn)之間的最大距離：max3
子樹A的最大節(jié)點(diǎn)間距離為max1俺亮，max2，max3中的最大值
根據(jù)以上分析疟呐，采用后序遍歷的方式脚曾，具體如下：- 后序遍歷二叉樹，對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行2中的信息收集
- 對(duì)左子樹產(chǎn)生Lmax1（非根節(jié)點(diǎn)間的最大距離）和Lmax2（節(jié)點(diǎn)和左子樹根節(jié)點(diǎn)間的最大距離）兩個(gè)信息
對(duì)右子樹產(chǎn)生Rmax1（非根節(jié)點(diǎn)間的最大距離）和Rmax2（節(jié)點(diǎn)和右子樹根節(jié)點(diǎn)間的最大距離）兩個(gè)信息 - 以當(dāng)前節(jié)點(diǎn)為根的子樹節(jié)點(diǎn)間的最大距離為max(Lmax1, Rmax1, Lmax2 + 1 + Rmax2)
- Lmax2 + 1和Rmax2 + 1分別為當(dāng)前節(jié)點(diǎn)左子樹中節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最大值和當(dāng)前節(jié)點(diǎn)右子樹中節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最大值启具，需要返回
編程中返回兩個(gè)信息可以通過返回長度為2的數(shù)組實(shí)現(xiàn)
在遞歸中維護(hù)當(dāng)前層的處理結(jié)果并返回給上一層可以通過更新全局變量實(shí)現(xiàn)
-
已知二叉樹頭結(jié)點(diǎn)為head本讥，其中所有節(jié)點(diǎn)都不一樣，請(qǐng)返回含有節(jié)點(diǎn)數(shù)最多的搜索二叉樹的頭節(jié)點(diǎn)
某子樹頭節(jié)點(diǎn)為A，出現(xiàn)搜索二叉樹的兩種情況：- 來自左子樹中的搜索二叉樹的頭結(jié)點(diǎn)為左孩子且左子樹上所有節(jié)點(diǎn)值小于A的節(jié)點(diǎn)值拷沸，來自右子樹中的搜索二叉樹的頭結(jié)點(diǎn)為右孩子且右子樹上所有節(jié)點(diǎn)值大于A的節(jié)點(diǎn)值色查，則以A為根的子樹為搜索二叉樹
- 不滿足以上情況則返回左、右子樹中節(jié)點(diǎn)多的搜索二叉樹
根據(jù)以上分析撞芍，采用后序遍歷的方式秧了，具體如下：
- 后序遍歷二叉樹，對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行如下信息收集
- 對(duì)每個(gè)節(jié)點(diǎn)的左子樹收集如下4個(gè)信息：左子樹上最大搜索子樹的頭結(jié)點(diǎn)序无、節(jié)點(diǎn)個(gè)數(shù)验毡、樹上的最小值、樹上的最大值帝嗡。
- 對(duì)每個(gè)節(jié)點(diǎn)的右子樹收集如下4個(gè)信息：右子樹上最大搜索子樹的頭結(jié)點(diǎn)晶通、節(jié)點(diǎn)個(gè)數(shù)、樹上的最小值丈探、樹上的最大值录择。
- 根據(jù)前兩步的信息判斷是否滿足出現(xiàn)搜索二叉樹的兩種情況
編程中返回四個(gè)信息可以通過返回長度為4的數(shù)組實(shí)現(xiàn)
在遞歸中維護(hù)當(dāng)前層的處理結(jié)果并返回給上一層可以通過更新全局變量實(shí)現(xiàn)
