同學(xué)，二叉樹(shù)的各種遍歷方式，我都幫你總結(jié)了，附有隊(duì)列堆棧圖解（鞏固基礎(chǔ)，強(qiáng)烈建議收藏）
靚仔靚女們大家好，我是java小杰要加油，今天我來(lái)分享一篇關(guān)于二叉樹(shù)的文章（建議收藏，便于鞏固基礎(chǔ)）。
看完此文leetcode至少解決八道題 掌握二叉樹(shù)的前序、中序、后序遍歷以及兩種不同的實(shí)現(xiàn)方式：遞歸與非遞歸 非遞歸時(shí)遍歷與層次遍歷時(shí)，有詳細(xì)的圖解表示隊(duì)列/棧中的元素是如何移動(dòng)的，有助于理解代碼的運(yùn)行
二叉樹(shù)介紹
二叉樹(shù)（binary tree） 是指樹(shù)中節(jié)點(diǎn)的度不大于2的有序樹(shù)，它是一種最簡(jiǎn)單且最重要的樹(shù)。
二叉樹(shù)的遞歸定義為： 二叉樹(shù)是一棵空樹(shù)，或者是一棵由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的，分別稱(chēng)作根的左子樹(shù)和右子樹(shù)組成的非空樹(shù)；左子樹(shù)和右子樹(shù)又同樣都是二叉樹(shù)
邏輯上二叉樹(shù)有五種基本形態(tài)，如圖所示 空二叉樹(shù) 只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù) 只有左子樹(shù) 完全二叉樹(shù) 只有右子樹(shù)
二叉樹(shù)相關(guān)屬性解釋?zhuān)?/strong>
結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向子樹(shù)分支的信息。 結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)擁有子樹(shù)的數(shù)目稱(chēng)為結(jié)點(diǎn)的度。 葉子結(jié)點(diǎn)：也稱(chēng)為終端結(jié)點(diǎn)，沒(méi)有子樹(shù)的結(jié)點(diǎn)或者度為零的結(jié)點(diǎn)。 分支結(jié)點(diǎn)：也稱(chēng)為非終端結(jié)點(diǎn)，度不為零的結(jié)點(diǎn)稱(chēng)為非終端結(jié)點(diǎn)。 樹(shù)的度：樹(shù)中所有結(jié)點(diǎn)的度的最大值。 結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開(kāi)始，假設(shè)根結(jié)點(diǎn)為第1層，根結(jié)點(diǎn)的子節(jié)點(diǎn)為第2層，依此類(lèi)推，如果某一個(gè)結(jié)點(diǎn)位于第L層，則其子節(jié)點(diǎn)位于第L+1層。 樹(shù)的深度：也稱(chēng)為樹(shù)的高度，樹(shù)中所有結(jié)點(diǎn)的層次最大值稱(chēng)為樹(shù)的深度。 有序樹(shù)：如果樹(shù)中各棵子樹(shù)的次序是有先后次序，則稱(chēng)該樹(shù)為有序樹(shù)。 無(wú)序樹(shù)：如果樹(shù)中各棵子樹(shù)的次序沒(méi)有先后次序，則稱(chēng)該樹(shù)為無(wú)序樹(shù)。
二叉樹(shù)遍歷方式
二叉樹(shù)遍歷方式分為三種 前序遍歷（根左右）：訪(fǎng)問(wèn)根結(jié)點(diǎn)，再訪(fǎng)問(wèn)左子樹(shù)、再訪(fǎng)問(wèn)右子樹(shù)。 中序遍歷（左根右）：先訪(fǎng)問(wèn)左子樹(shù)，再訪(fǎng)問(wèn)根結(jié)點(diǎn)、再訪(fǎng)問(wèn)右子樹(shù)。 后續(xù)遍歷（左右根）：先訪(fǎng)問(wèn)左子樹(shù)，再訪(fǎng)問(wèn)右子樹(shù)，再訪(fǎng)問(wèn)根結(jié)點(diǎn)。
例如一個(gè)這個(gè)樣子的二叉樹(shù)，按三種遍歷方法分別遍歷，輸出的結(jié)果分別是
前序遍歷：ABDECFG 中序遍歷：DBEAFCG 后續(xù)遍歷：DEBFGCA
下面我們一起來(lái)用代碼實(shí)現(xiàn)下這三種遍歷
注：以上前序、中序、后序每一種遍歷方式都有遞歸和非遞歸兩種實(shí)現(xiàn)方法 前序遍歷就是深度優(yōu)先遍歷（DFS） 層次遍歷就是廣度優(yōu)先遍歷（BFS）
二叉樹(shù)遞歸遍歷
* 前序遍歷 （LeetCode ?144）
class?Solution?{
????//聲明列表
????ArrayList?list?=?new?ArrayList<>();
????public?List?preorderTraversal(TreeNode?root)? {
????????//?如果根節(jié)點(diǎn)為空，則直接返回空列表
????????if?(root?==?null){
????????????return??new?ArrayList<>();
????????}
????????//節(jié)點(diǎn)不為空，將節(jié)點(diǎn)的值添加進(jìn)列表中????
????????list.add(root.val);
????????//判斷此節(jié)點(diǎn)的左節(jié)點(diǎn)是否為空，如果不為空則將遞歸遍歷左子樹(shù)
????????if?(root.left?!=?null){
????????????preorderTraversal(root.left);
????????}
????????//判斷此節(jié)點(diǎn)的右節(jié)點(diǎn)是否為空，如果不為空則將遞歸遍歷右子樹(shù)
????????if?(root.right?!=?null){
????????????preorderTraversal(root.right);
????????}
????????//最后返回列表
????????return?list;
????}
}
中序遍歷（LeetCode ?94）
class?Solution?{
????//聲明列表
????ArrayList?list?=?new?ArrayList<>();
????public?List?inorderTraversal(TreeNode?root)? {
????????//?如果根節(jié)點(diǎn)為空，則直接返回空列表
????????if?(root?==?null){
????????????return??new?ArrayList<>();
????????}
????????//判斷此節(jié)點(diǎn)的左節(jié)點(diǎn)是否為空，如果不為空則將遞歸遍歷此節(jié)點(diǎn)的左子樹(shù)
????????if?(root.left?!=?null){
????????????inorderTraversal(root.left);
????????}
????????//節(jié)點(diǎn)不為空，將節(jié)點(diǎn)的值添加進(jìn)列表中
????????list.add(root.val);
????????//判斷此節(jié)點(diǎn)的右節(jié)點(diǎn)是否為空，如果不為空則將遞歸遍歷此節(jié)點(diǎn)的右子樹(shù)
????????if?(root.right?!=?null){
????????????inorderTraversal(root.right);
????????}
????????//最后返回列表
????????return?list;
????}
}
后續(xù)遍歷（LeetCode ?145）
class?Solution?{
????//聲明列表
????ArrayList?list?=?new?ArrayList<>();
????public?List?postorderTraversal(TreeNode?root)? {
????????//?如果根節(jié)點(diǎn)為空，則直接返回空列表
????????if?(root?==?null){
????????????return??new?ArrayList<>();
????????}
????????//判斷此節(jié)點(diǎn)的左節(jié)點(diǎn)是否為空，如果不為空則將遞歸遍歷此節(jié)點(diǎn)的左子樹(shù)
????????if?(root.left?!=?null){
????????????postorderTraversal(root.left);
????????}
????????//判斷此節(jié)點(diǎn)的右節(jié)點(diǎn)是否為空，如果不為空則將遞歸遍歷此節(jié)點(diǎn)的右子樹(shù)
????????if?(root.right?!=?null){
????????????postorderTraversal(root.right);
????????}
????????//節(jié)點(diǎn)不為空，將節(jié)點(diǎn)的值添加進(jìn)列表中
????????list.add(root.val);
????????//最后返回列表
????????return?list;
????}
}
我們通過(guò)觀(guān)察發(fā)現(xiàn)，這代碼怎么這么像，是的就是很像，他們唯一的區(qū)別就是list.add(root.val);代碼的位置不一樣，這行代碼就代表文中的 遍歷（訪(fǎng)問(wèn)）
下圖中為前序遍歷（根左右）
下圖中為中序遍歷（左根右）
下圖中為后序遍歷（左右根）
二叉樹(shù)非遞歸遍歷
用到棧（FILO 先進(jìn)后出的特性） 每段代碼后，都有棧和其中元素的關(guān)系具體過(guò)程，建議靜下心來(lái)慢慢看，有助于理解代碼如何運(yùn)行
前序遍歷
class?Solution?{
????List?list?=???new?ArrayList();
????public?List?preorderTraversal(TreeNode?root)? {
????????//如果根節(jié)點(diǎn)為空，則直接返回空列表
????????if(root==null){
????????????return??new?ArrayList();
????????}
????????//聲明一個(gè)棧
????????Stack?stack?=?new?Stack<>();
????????//將節(jié)點(diǎn)入棧
????????stack.push(root);
????????//如果棧不為空
????????while?(!stack.empty()){
????????????//從棧彈出這個(gè)節(jié)點(diǎn)
????????????TreeNode?node?=?stack.pop();
????????????//添加進(jìn)列表中
????????????list.add(node.val);
????????????//?如果這個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)不為空
????????????if?(node.right!=null){
????????????????//?將其入棧??因?yàn)闂Ｊ窍冗M(jìn)后出，所以先壓棧右子節(jié)點(diǎn)??后出
????????????????stack.push(node.right);
????????????}
????????????//?如果這個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)不為空
????????????if?(node.left!=null){
????????????????//?將其入棧?因?yàn)闂Ｊ窍冗M(jìn)后出，所以后壓棧左子節(jié)點(diǎn)?先出
????????????}
????????}
????????//返回列表
????????return?list;
????}
}
中序遍歷
class?Solution?{
????public?List?inorderTraversal(TreeNode?root)? {
????????//判斷節(jié)點(diǎn)是否為空，為空的話(huà)直接返回空列表
????????if?(root?==?null){
????????????return?new?ArrayList();
????????}
????????//聲明列表存儲(chǔ)結(jié)果
????????List?list?=??new?ArrayList();
????????//聲明一個(gè)棧
????????Stack?stack?=?new?Stack<>();
????????//當(dāng)節(jié)點(diǎn)不為空或者棧不為空時(shí)
????????while?(root?!=?null?||?!stack.empty()){
????????????//當(dāng)節(jié)點(diǎn)不為空時(shí)
????????????while?(root?!=?null){
????????????????//將節(jié)點(diǎn)壓棧
????????????????stack.push(root);
????????????????//將節(jié)點(diǎn)指向其左子節(jié)點(diǎn)
????????????????root?=?root.left;
????????????}
????????????//如果棧不為空
????????????if?(!stack.empty()){
????????????????//將棧里元素彈出來(lái)
????????????????TreeNode?node?=?stack.pop();
????????????????//添加進(jìn)列表中
????????????????list.add(node.val);
????????????????//將節(jié)點(diǎn)指向其右子節(jié)點(diǎn)
????????????????root?=?node.right;
????????????}
????????}
????????return?list;
????}
}
后序遍歷
class?Solution?{
????public?List?postorderTraversal(TreeNode?root)? {
????????//?如果根節(jié)點(diǎn)為空，則直接返回空列表
????????if?(root?==?null){
????????????return??new?ArrayList<>();
????????}
????????//聲明列表
????????ArrayList?list?=?new?ArrayList<>();
????????//聲明棧A
????????Stack?stackA?=?new?Stack();
????????//聲明棧B
????????Stack?stackB?=?new?Stack();
????????//將次元素壓入棧A
????????stackA.push(root);
????????//當(dāng)棧A不為空時(shí)
????????while?(!stackA.empty()){
????????????//取出其中壓入的元素
????????????TreeNode?node?=?stackA.pop();
????????????//壓入棧B中
????????????stackB.push(node);
????????????//當(dāng)此節(jié)點(diǎn)左子節(jié)點(diǎn)不為空時(shí)
????????????if?(node.left?!=?null){
????????????????//壓入棧A
????????????????stackA.push(node.left);
????????????}
????????????//當(dāng)此節(jié)點(diǎn)右子節(jié)點(diǎn)不為空時(shí)
????????????if?(node.right?!=?null){
????????????????//壓入棧A
????????????????stackA.push(node.right);
????????????}
????????}
????????//當(dāng)棧B不為空時(shí)
????????while?(!stackB.empty()){
????????????//取出其元素并且添加至列表中
????????????TreeNode?node?=?stackB.pop();
????????????list.add(node.val);
????????}
????????//最后返回列表
????????return?list;
????}
}
二叉樹(shù)層序遍歷（BFS）
LeetCode ?102 ? 二叉樹(shù)的層序遍歷 用到隊(duì)列（FIFO 先進(jìn)先出的特性）代碼后有隊(duì)列和其中元素的關(guān)系具體過(guò)程，建議靜下心來(lái)慢慢看，有助于理解代碼如何運(yùn)行
class?Solution?{
????public?List>?levelOrder(TreeNode?root)?{
????????if?(root?==?null)?{
????????????return?new?ArrayList>();
????????}
????????//?聲明一個(gè)列表存儲(chǔ)每一行的數(shù)據(jù)
????????List>?result?=?new?ArrayList<>();
????????//聲明一個(gè)隊(duì)列
????????LinkedList?queue?=?new?LinkedList<>();
????????//如果根節(jié)點(diǎn)不為空，將其入隊(duì)
????????queue.offer(root);
????????//當(dāng)隊(duì)列不為空時(shí)，代表隊(duì)列里有數(shù)據(jù)
????????while?(!queue.isEmpty())?{
????????????//存儲(chǔ)每一行的數(shù)據(jù)line
????????????List?line?=?new?ArrayList();
????????????//保存隊(duì)列中現(xiàn)有數(shù)據(jù)的個(gè)數(shù)，這些就是要添加至每一行列表的值
????????????int?size?=?queue.size();
????????????for?(int?i=0;i????????????//取出隊(duì)列的節(jié)點(diǎn)?（FIFO?先進(jìn)先出）
????????????TreeNode?node?=?queue.poll();
????????????line.add(node.val);
??????????????if?(node.left?!=?null)?{
??????????????????queue.offer(node.left);
??????????????}
??????????????if?(node.right?!=?null)?{
??????????????????queue.offer(node.right);
??????????????}
????????????}
????????????result.add(line);
????????}
????????return?result;
????}
}
leetcode二叉樹(shù)相關(guān)練習(xí)
我們看到了這里，對(duì)二叉樹(shù)的前序（DFS）、中序、后序、遞歸/非遞歸以及層次遍歷(BFS)都有了一定的了解（如果上面的圖都消化了的話(huà)）
然后我們趁熱打鐵來(lái)幾道leetcode題目試試手?。傮w代碼和上面只有稍微的改動(dòng)，因?yàn)榇笾滤枷胧且粯拥?，把上面的?nèi)容都消化了的話(huà)就很簡(jiǎn)單啦）
leetcode-257 二叉樹(shù)的所有路徑
class?Solution?{
????public?List?binaryTreePaths(TreeNode?root)? {
????????if?(root?==?null){
????????????return?new?ArrayList<>();
????????}
????????ArrayList?list?=?new?ArrayList<>();
????????Stack?stack?=?new?Stack();
????????//這個(gè)棧存儲(chǔ)路徑，與上一個(gè)存儲(chǔ)節(jié)點(diǎn)的棧一樣的操作
????????Stack?path?=?new?Stack();
????????stack.push(root);
????????path.push(root.val+"");
????????while?(!stack.empty()){
????????????TreeNode?node?=?stack.pop();
????????????String?p?=?path.pop();
????????????//當(dāng)是葉子節(jié)點(diǎn)的時(shí)候，此時(shí)棧中的路徑即為一條完整的路徑，可以加入到結(jié)果中
????????????if?(node.right?==?null?&&?node.left?==?null?){
????????????????list.add(p);
????????????}
????????????//如果右子節(jié)點(diǎn)不為空
????????????if?(node.right?!=?null){
????????????????stack.push(node.right);
????????????????//將臨時(shí)路徑繼續(xù)壓棧
????????????????path.push(p+"->"+node.right.val);
????????????}
????????????//如果左子節(jié)點(diǎn)不為空
????????????if?(node.left?!=?null){
????????????????stack.push(node.left);
????????????????//將臨時(shí)路徑繼續(xù)壓棧
????????????????path.push(p+"->"+node.left.val);
????????????}
????????}
????????return?list;
????}
}
leetcode-104 二叉樹(shù)的最大深度 與 劍指offer 55-I 相同
class?Solution?{
????public?int?maxDepth(TreeNode?root)?{
???????if?(root?==?null){
???????????return?0;
???????}
????????LinkedList?queue?=?new?LinkedList<>();
????????int?result?=?0;
????????queue.offer(root);
????????while?(!queue.isEmpty()){
????????????//層數(shù)+1
????????????result++;
????????????//這是當(dāng)前層的節(jié)點(diǎn)的個(gè)數(shù)
????????????int?size?=?queue.size();
????????????for?(int?i=0;i????????????????//要將其全部出隊(duì)后，才可以再次計(jì)數(shù)
????????????????TreeNode?node?=?queue.poll();
????????????????if?(node.left?!=?null){
????????????????????//如果出隊(duì)的節(jié)點(diǎn)還有左子節(jié)點(diǎn)，就入隊(duì)
????????????????????queue.offer(node.left);
????????????????}
????????????????if?(node.right?!=?null){
????????????????????//如果出隊(duì)的節(jié)點(diǎn)還有右子節(jié)點(diǎn)，就入隊(duì)
????????????????????queue.offer(node.right);
????????????????}
????????????}
????????}
????????//返回層數(shù)
????????return?result;
????}
}
leetcode-107 二叉樹(shù)的層序遍歷2
class?Solution?{
????public?List>?levelOrderBottom(TreeNode?root)?{
????????if?(root?==?null){
????????????return?new?ArrayList>()?;
????????}
????????List>?result?=?new?ArrayList>()?;
????????LinkedList?queue?=?new?LinkedList<>();
????????//聲明一個(gè)棧，用來(lái)存儲(chǔ)每一層的節(jié)點(diǎn)
????????Stack?>?stack?=?new?Stack<>();
????????queue.offer(root);
????????while?(!queue.isEmpty()){
????????????int?size?=?queue.size();
????????????ArrayList?list?=?new?ArrayList<>();
????????????for?(int?i=0;i????????????????TreeNode?node?=?queue.poll();
????????????????list.add(node.val);
????????????????if?(node.left?!=?null){
????????????????????queue.offer(node.left);
????????????????}
????????????????if?(node.right?!=?null){
????????????????????queue.offer(node.right);
????????????????}
????????????}
????????????//將這一層的節(jié)點(diǎn)壓入棧中
????????????stack.push(list);
????????}
????????//當(dāng)棧不為空時(shí)，彈出結(jié)果，從而達(dá)到從下往上遍歷二叉樹(shù)的效果
????????while?(!stack.isEmpty()){
????????????ArrayList?list?=?stack.pop();
????????????result.add(list);
????????}
????????return?result;
????}
}
總結(jié)
我們通過(guò)這篇文章，至少可以解決leetcode上以下幾道題目
前序遍歷 （LeetCode ?144）
中序遍歷（LeetCode ?94）
后續(xù)遍歷（LeetCode ?145）
LeetCode ?102 ? 二叉樹(shù)的層序遍歷
leetcode-257 二叉樹(shù)的所有路徑
leetcode-104 二叉樹(shù)的最大深度 與 劍指offer 55-I 相同
leetcode-107 二叉樹(shù)的層序遍歷2
往期精彩推薦
京東面試官問(wèn)我：“聊聊MySql事務(wù),MVCC？（好文，建議收藏）” 你好，我叫AQS（系列一：加鎖） 京東這道面試題你會(huì)嗎？ ？線(xiàn)程池為什么可以復(fù)用，我是蒙圈了。。。 學(xué)會(huì)了volatile，你變心了，我看到了
絮絮叨叨
如果大家覺(jué)得這篇文章對(duì)自己有一點(diǎn)點(diǎn)幫助的話(huà)，歡迎關(guān)注此公眾號(hào) java小杰要加油，小杰非常希望各位可以點(diǎn)擊一下屏幕下方的
點(diǎn)贊、在看、收藏、分享。
（好家伙，劉關(guān)張直接在我嘴里結(jié)義）
隨手一個(gè)點(diǎn)擊，我將無(wú)法忘記，這是我堅(jiān)持創(chuàng)作的最大動(dòng)力！
非常歡迎 各位號(hào)主讀者一起交流學(xué)習(xí)，互相開(kāi)白轉(zhuǎn)發(fā)，網(wǎng)絡(luò)一線(xiàn)牽，珍惜這段緣
若文章有誤歡迎指出，靚仔靚女們，我們下篇文章見(jiàn)，掃一掃，開(kāi)啟我們的故事
評(píng)論
圖片
表情