前言
二叉樹遍歷是非常經(jīng)典的算法題蛋铆，也是二叉樹的一道基礎(chǔ)算法題。
但是在平常的筆試面試中，其出現(xiàn)的頻率其實并不是特別的高衡瓶，我推測是這種題目相對來說比較基礎(chǔ)，算是一個基礎(chǔ)知識點牲证。
比如劍指offer中出現(xiàn)的后序遍歷題目哮针，是給出一個數(shù)字序列，讓你判斷是不是平衡二叉樹后序遍歷序列坦袍，這樣出題的難度比直接讓你寫后序遍歷難很多十厢。
但是，二叉樹遍歷容易嗎捂齐？在遞歸方法下蛮放，前中后序遍歷都是一個思路，理解起來也比較容易奠宜。
但是只是用迭代的話包颁，二叉樹遍歷其實是有難度的瞻想！，這也是為什么LeetCode會在這三題題目的下方寫出進階: 遞歸算法很簡單娩嚼，你可以通過迭代算法完成嗎蘑险？這句話了。
本文的主要內(nèi)容如下：
-
題目定義：
- 上篇：二叉樹前序待锈、中序漠其、后序遍歷
- 下篇：層序遍歷、其他遍歷相關(guān)題型
- 解題思路：遞歸 + 迭代+ 莫里斯Morris遍歷
- 解題代碼：Java + Python
注1：本文中的解題思路會盡量的全面竿音，但是解題方法千變?nèi)f化和屎，有很多奇技淫巧我不會去介紹，大家有興趣可以自行擴展學習春瞬。
注2：本文中的代碼會盡量簡單柴信，易懂，并不會去追求極致的寫法（比如：在一行內(nèi)完成宽气，使用各種非正式的庫等）随常。
正文
二叉樹的定義
最多有兩棵子樹的樹被稱為二叉樹
二叉樹下還有很多種特殊的二叉樹，下方簡單介紹幾種常用的萄涯。
滿二叉樹
二叉樹中所有非葉子結(jié)點的度都是2绪氛，且葉子結(jié)點都在同一層次上
完全二叉樹（可以不滿）
如果一個二叉樹與滿二叉樹前m個節(jié)點的結(jié)構(gòu)相同，這樣的二叉樹被稱為完全二叉樹涝影。也就是說枣察，如果把滿二叉樹從右至左、從下往上刪除一些節(jié)點燃逻，剩余的結(jié)構(gòu)就構(gòu)成完全二叉樹序目。
二叉搜索樹
二叉查找樹（BinarySearch Tree，也叫二叉搜索樹伯襟，或稱二叉排序樹Binary Sort Tree）或者是一棵空樹猿涨，或者是具有下列性質(zhì)的二叉樹：
- 若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值姆怪；
- 若它的右子樹不空叛赚，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
- 它的左稽揭、右子樹也分別為二叉排序樹
二叉樹前中后序遍歷
遍歷方法
前序遍歷：根結(jié)點 ---> 左子樹 ---> 右子樹
中序遍歷：左子樹---> 根結(jié)點 ---> 右子樹
后序遍歷：左子樹 ---> 右子樹 ---> 根結(jié)點
題目介紹
前序遍歷
LeetCode題目地址：
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
輸入: [1,null,2,3]
1
\
2
/
3
輸出: [1,2,3]
中序遍歷
LeetCode題目地址：
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
輸入: [1,null,2,3]
1
\
2
/
3
輸出: [1,3,2]
后序遍歷
LeetCode題目地址：
https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
輸入: [1,null,2,3]
1
\
2
/
3
輸出: [3,2,1]
解題思路詳解與代碼實現(xiàn)
二叉樹的前中后序遍歷俺附，主要就是兩種思路，一種是遞歸淀衣，一種是迭代。
如果看到這里還沒有感覺召调，不用擔心膨桥，先直接往下看蛮浑，第一個代碼（前序遍歷的遞歸思路）會幫助你提升感覺。
遞歸思路
遞歸思路是最容易理解的思路只嚣，并且前中后序遍歷都相同沮稚。
比如前序遍歷，在遞歸的函數(shù)里册舞，先往結(jié)果數(shù)組里加入根節(jié)點蕴掏，然后加入根節(jié)點的左節(jié)點，然后加入根節(jié)點的右節(jié)點调鲸。最后所有遞歸的函數(shù)運行完畢盛杰，結(jié)果集就已經(jīng)完成了。
中序和后序的思路相同藐石，就不再贅述了即供。
前序遍歷
Java：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
preorder(root, result);
return result;
}
private static List<Integer> preorder(TreeNode root, List<Integer> result) {
if (root != null) {
result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
}
return result;
}
}
Python：
class Solution(object):
def _preorderTraversal(self, root, result):
if root:
result.append(root.val)
self._preorderTraversal(root.left, result)
self._preorderTraversal(root.right, result)
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root == None:
return []
result = []
self._preorderTraversal(root, result)
return result
中序遍歷
Java：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
result = inorder(root, result);
return result;
}
private static List<Integer> inorder(TreeNode root, List<Integer> result) {
if (root != null) {
inorder(root.left, result);
result.add(root.val);
inorder(root.right, result);
}
return result;
}
}
Python：
class Solution(object):
def generate(self, root, result):
if root:
self.inorder(root.left, list)
result.append(root.val)
self.inorder(root.right, list)
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
result = []
self.generate(root, result)
return result
后序遍歷
Java：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
result = postorder(root, result);
return result;
}
private static List<Integer> postorder(TreeNode root, List<Integer> result) {
if (root != null) {
postorder(root.left, result);
postorder(root.right, result);
result.add(root.val);
}
return result;
}
}
Python：
class Solution(object):
def _postorderTraversal(self, root, result):
if root:
self._postorderTraversal(root.left, result)
self._postorderTraversal(root.right, result)
result.append(root.val)
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root == None:
return []
result = []
self._postorderTraversal(root, result)
return result
迭代思路
前序遍歷
我們需要一個棧來完成遍歷。
1.根節(jié)點入棧
2.取出節(jié)點于微，值加入結(jié)果逗嫡，然后先加右，后加左株依。
3.重復2
這樣就得到了 根節(jié)點——左子樹——右子樹 的遍歷結(jié)果集驱证。
Java：
來自官方題解
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
stack.add(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pollLast();
output.add(node.val);
if (node.right != null) {
stack.add(node.right);
}
if (node.left != null) {
stack.add(node.left);
}
}
return output;
}
Python：
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ret = []
stack = [root]
while stack:
node = stack.pop()
if node:
ret.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return ret
中序遍歷
還是使用一個棧來解決問題。
步驟如下：
1
/ \
2 3
/ \ / \
4 5 6 7
我們將根節(jié)點1入棧恋腕，如果有左孩子抹锄，依次入棧，那么入棧順序為：1吗坚，2祈远，4。由于4的左子樹為空商源，停止入棧车份，此時棧為{1牡彻，2扫沼，4}。
此時將4出棧庄吼，并遍歷4缎除，由于4也沒有右孩子，那么根據(jù)中序遍歷的規(guī)則总寻，我們顯然應該繼續(xù)遍歷4的父親2器罐，情況是這樣。所以我們繼續(xù)將2出棧并遍歷2渐行，2存在右孩子轰坊，將5入棧铸董，此時棧為{1，5}肴沫。
5沒有孩子粟害，則將5出棧并遍歷5，這也符合中序遍歷的規(guī)則颤芬。此時棧為{1}悲幅。
1有右孩子，則將1出棧并遍歷1站蝠，然后將右孩子3入棧汰具，并繼續(xù)以上三個步驟即可。
棧的變化過程：{1}->{1,2}->{1,2,4}->{1,2}->{1}->{1,5}->{1}->{}->{3}->{3,6}->{3}->{}->{7}->{}沉衣。
總結(jié)：從根節(jié)點遍歷郁副，先放入所有有左孩子的節(jié)點直到?jīng)]有，然后出棧豌习，出棧的時候就將出棧的數(shù)字放入結(jié)果集存谎，然后看其有沒有右孩子，有的話右孩子入棧肥隆。
Java：
官方題解
public class Solution {
public List <Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
}
Python：
class Solution:
# @param root, a tree node
# @return a list of integers
def inorderTraversal(self, root):
result = []
stack = []
while root or stack:
if root:
stack.append(root)
root = root.left
else:
root = stack.pop()
result.append(root.val)
root = root.right
return result
后序遍歷
將數(shù)組輸出為右子樹-左子樹-根節(jié)點既荚。最后，再將數(shù)組倒序輸出栋艳，形成后序遍歷恰聘。這樣代碼并不用很繁瑣，也能做完迭代吸占。
是不是似曾相識晴叨，沒錯，和前序遍歷的迭代幾乎一樣矾屯，僅僅是先放右節(jié)點再放左節(jié)點變成了先放左節(jié)點再放右節(jié)點兼蕊，然后倒序輸出。
Java：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
stack.add(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pollLast();
output.addFirst(node.val);
if (node.left != null) {
stack.add(node.left);
}
if (node.right != null) {
stack.add(node.right);
}
}
return output;
}
}
Python：
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root is None:
return []
ret = []
stack = [root]
while stack:
node = stack.pop()
if node:
ret.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return ret[::-1]
所以迭代方式件蚕，前后序是非常類似的孙技，中序遍歷可能需要單獨理解下。
莫里斯遍歷
二叉樹常規(guī)的遍歷方法是用遞歸來實現(xiàn)的排作，這種方法一般都需要O(n)的空間復雜度和O(n)的時間復雜度牵啦。而Morris方法實現(xiàn)的是O(1)的空間復雜度和O(n)的時間復雜度。
我們知道妄痪，遍歷二叉樹時哈雏，最大的難點在于，遍歷到子節(jié)點的時候怎樣重新返回到父節(jié)點（假設(shè)節(jié)點中沒有指向父節(jié)點的p指針），由于不能用棧作為輔助空間裳瘪。(不然就是普通迭代方法)履因。
為了解決這個問題，Morris方法用到了線索二叉樹（threaded binary tree）的概念盹愚。在Morris方法中不需要為每個節(jié)點額外分配指針指向其前驅(qū)（predecessor）和后繼節(jié)點（successor），只需要利用葉子節(jié)點中的左右空指針指向某種順序遍歷下的前驅(qū)節(jié)點或后繼節(jié)點就可以了站故。
聽不懂沒關(guān)系皆怕，下面使用中序遍歷作為例子來理解莫里斯遍歷到底是什么意思，例子來自LeetCode官方題解：
中序遍歷
Step 1: 將當前節(jié)點current初始化為根節(jié)點
Step 2: While current不為空西篓，
若current沒有左子節(jié)點
a. 將current添加到輸出
b. 進入右子樹愈腾，亦即, current = current.right
否則
a. 在current的左子樹中，令current成為最右側(cè)節(jié)點的右子節(jié)點
b. 進入左子樹岂津，亦即虱黄，current = current.left
1
/ \
2 3
/ \ /
4 5 6
首先，1 是根節(jié)點吮成，所以將 current 初始化為 1橱乱。1 有左子節(jié)點 2，current 的左子樹是
2
/ \
4 5
在此左子樹中最右側(cè)的節(jié)點是 5粱甫，于是將 current(1) 作為 5 的右子節(jié)點泳叠。令 current = cuurent.left (current = 2)。 現(xiàn)在二叉樹的形狀為:
2
/ \
4 5
\
1
\
3
/
6
對于 current(2)茶宵，其左子節(jié)點為4危纫，我們可以繼續(xù)上述過程
4
\
2
\
5
\
1
\
3
/
6
Java：
class Solution {
public List < Integer > inorderTraversal(TreeNode root) {
List < Integer > res = new ArrayList < > ();
TreeNode curr = root;
TreeNode pre;
while (curr != null) {
if (curr.left == null) {
res.add(curr.val);
curr = curr.right; // move to next right node
} else { // has a left subtree
pre = curr.left;
while (pre.right != null) { // find rightmost
pre = pre.right;
}
pre.right = curr; // put cur after the pre node
TreeNode temp = curr; // store cur node
curr = curr.left; // move cur to the top of the new tree
temp.left = null; // original cur left be null, avoid infinite loops
}
}
return res;
}
}
前序遍歷
理解了中序遍歷，前序和后序遍歷相對來說也就更容易理解了乌庶。所以前序和后序貼了思路种蝶，代碼我也沒自己寫后submit，在這里就不放了瞒大。
算法的思路是從當前節(jié)點向下訪問先序遍歷的前驅(qū)節(jié)點螃征，每個前驅(qū)節(jié)點都恰好被訪問兩次。
首先從當前節(jié)點開始糠赦，向左孩子走一步然后沿著右孩子一直向下訪問会傲，直到到達一個葉子節(jié)點（當前節(jié)點的中序遍歷前驅(qū)節(jié)點），所以我們更新輸出并建立一條偽邊 predecessor.right = root 更新這個前驅(qū)的下一個點拙泽。如果我們第二次訪問到前驅(qū)節(jié)點淌山，由于已經(jīng)指向了當前節(jié)點，我們移除偽邊并移動到下一個頂點顾瞻。
后序遍歷
后續(xù)遍歷稍顯復雜泼疑，需要建立一個臨時節(jié)點dump，令其左孩子是root荷荤。并且還需要一個子過程退渗，就是倒序輸出某兩個節(jié)點之間路徑上的各個節(jié)點移稳。
步驟：
當前節(jié)點設(shè)置為臨時節(jié)點dump。
如果當前節(jié)點的左孩子為空会油，則將其右孩子作為當前節(jié)點个粱。
如果當前節(jié)點的左孩子不為空，在當前節(jié)點的左子樹中找到當前節(jié)點在中序遍歷下的前驅(qū)節(jié)點翻翩。
a) 如果前驅(qū)節(jié)點的右孩子為空都许，將它的右孩子設(shè)置為當前節(jié)點。當前節(jié)點更新為當前節(jié)點的左孩子嫂冻。
b) 如果前驅(qū)節(jié)點的右孩子為當前節(jié)點胶征，將它的右孩子重新設(shè)為空。倒序輸出從當前節(jié)點的左孩子到該前驅(qū)節(jié)點這條路徑上的所有節(jié)點桨仿。當前節(jié)點更新為當前節(jié)點的右孩子睛低。
重復以上1、2直到當前節(jié)點為空服傍。
