淺談二叉樹遍歷
這里就對(duì)二叉樹的遍歷方式進(jìn)行總結(jié)
基于遞歸的遍歷
前序遍歷
前序遍歷：即對(duì)二叉樹按照當(dāng)前節(jié)點(diǎn)、左子樹、右子樹的順序進(jìn)行遍歷。顯然借助遞歸，非常容易實(shí)現(xiàn)、理解
/**
* 基于遞歸的前序遍歷
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
dfs(root, list);
return list;
}
private void dfs(TreeNode cur, List<Integer> list) {
if( cur==null ) {
return;
}
// 1. 處理當(dāng)前節(jié)點(diǎn)
list.add( cur.val );
// 2. 處理左子樹
dfs(cur.left, list);
// 3. 處理右子樹
dfs(cur.right, list);
}
}
中序遍歷
中序遍歷：即對(duì)二叉樹按照左子樹、當(dāng)前節(jié)點(diǎn)、右子樹的順序進(jìn)行遍歷。顯然借助遞歸，非常容易實(shí)現(xiàn)、理解
/**
* 基于遞歸的中序遍歷
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
dfs(root, list);
return list;
}
private void dfs(TreeNode cur, List<Integer> list) {
if( cur==null ) {
return;
}
// 1. 處理左子樹
dfs(cur.left, list);
// 2. 處理當(dāng)前節(jié)點(diǎn)
list.add( cur.val );
// 3. 處理右子樹
dfs(cur.right, list);
}
}
后序遍歷
后序遍歷：即對(duì)二叉樹按照左子樹、右子樹、當(dāng)前節(jié)點(diǎn)的順序進(jìn)行遍歷。顯然借助遞歸，非常容易實(shí)現(xiàn)、理解
/**
* 基于遞歸的后序遍歷
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
dfs(root, list);
return list;
}
private void dfs(TreeNode cur, List<Integer> list) {
if( cur==null ) {
return;
}
// 1. 處理左子樹
dfs(cur.left, list);
// 2. 處理右子樹
dfs(cur.right, list);
// 3. 處理當(dāng)前節(jié)點(diǎn)
list.add( cur.val );
}
}
基于迭代的遍歷
前序遍歷
不同于遞歸隱式維護(hù)棧的便捷，在通過迭代進(jìn)行遍歷時(shí)需要我們顯式地維護(hù)一個(gè)棧。具體地，在前序遍歷當(dāng)中。首先需要處理對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行處理、然后沿著左子樹一直入棧。當(dāng)左子樹遍歷完畢, 通過出棧獲取父節(jié)點(diǎn)來對(duì)右子樹再進(jìn)行處理
/**
* 基于迭代的前序遍歷
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
while ( root!=null || !stack.isEmpty() ) {
while (root!=null) {
// 先處理當(dāng)前節(jié)點(diǎn)
res.add( root.val );
// 然后沿左子樹一直入棧
stack.addLast( root );
root = root.left;
}
// 左子樹遍歷完畢, 通過父節(jié)點(diǎn)來對(duì)右子樹再進(jìn)行處理
TreeNode parent = stack.removeLast();
root = parent.right;
}
return res;
}
}
中序遍歷
不同于遞歸隱式維護(hù)棧的便捷，在通過迭代進(jìn)行遍歷時(shí)需要我們顯式地維護(hù)一個(gè)棧。具體地，在中序遍歷當(dāng)中。首先沿著左子樹一直入棧。當(dāng)左子樹遍歷完畢, 通過出棧獲取父節(jié)點(diǎn)并對(duì)其進(jìn)行處理，最后對(duì)右子樹再進(jìn)行處理
/**
* 基于迭代的中序遍歷
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
while ( root!=null || !stack.isEmpty() ) {
while ( root!=null ) {
// 先沿左子樹一直入棧
stack.addLast( root );
root = root.left;
}
// 左子樹遍歷完畢, 獲取父節(jié)點(diǎn)
TreeNode parent = stack.removeLast();
// 處理父節(jié)點(diǎn)的值
res.add( parent.val );
// 通過父節(jié)點(diǎn)對(duì)右子樹再進(jìn)行處理
root = parent.right;
}
return res;
}
}
后序遍歷
后序遍歷的順序是左、右、當(dāng)前。如果直接使用棧按這個(gè)順序進(jìn)行遍歷輸出會(huì)比較麻煩。故我們可以先按照當(dāng)前、右、左的順序進(jìn)行迭代遍歷，顯然這個(gè)過程與前序遍歷非常類似，只是需要把代碼中涉及左、右子樹的調(diào)換下即可。最后對(duì)遍歷結(jié)果進(jìn)行翻轉(zhuǎn)。這樣遍歷結(jié)果就由當(dāng)前、右、左 就變?yōu)?左、右、當(dāng)前。即我們所需的后序遍歷結(jié)果
/**
* 基于迭代的后序遍歷
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
// 先按 根、右、左 的順序進(jìn)行遍歷
while ( root!=null || !stack.isEmpty() ) {
while (root!=null) {
// 先處理當(dāng)前節(jié)點(diǎn)
res.add( root.val );
// 然后沿右子樹一直入棧
stack.addLast( root );
root = root.right;
}
// 右子樹遍歷完畢, 通過父節(jié)點(diǎn)獲取左子樹再進(jìn)行處理
TreeNode parent = stack.removeLast();
root = parent.left;
}
// 對(duì)遍歷結(jié)果進(jìn)行翻轉(zhuǎn)
// 這樣遍歷結(jié)果就由 根、右、左 就變?yōu)?nbsp;左、右、根, 即后序遍歷
Collections.reverse( res );
return res;
}
}
層序遍歷
對(duì)于二叉樹的層序遍歷就簡單很多了。我們借助隊(duì)列的FIFO特性即可輕松實(shí)現(xiàn)
class Solution {
public List<Integer> levelOrder(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while ( !queue.isEmpty() ) {
// 彈出隊(duì)首元素, 進(jìn)行處理
TreeNode cur = queue.poll();
res.add( node.val );
// 將當(dāng)前節(jié)點(diǎn)的左、右子節(jié)點(diǎn)加入隊(duì)列
if( node.left != null ) {
queue.add( node.left );
}
if( node.right != null ) {
queue.add( node.right );
}
}
return res;
}
}
基于Morris算法的遍歷
基本原理
Morris算法為二叉樹的遍歷提供了新的思路，其通過充分利用樹中葉子節(jié)點(diǎn)存在大量空指針這一特點(diǎn)。實(shí)現(xiàn)了常數(shù)級(jí)別的空間復(fù)雜度。在進(jìn)一步介紹該算法之前，我們先來說明一個(gè)概念——mostRight節(jié)點(diǎn)。其用于表示當(dāng)前節(jié)點(diǎn)cur的左子樹的最右節(jié)點(diǎn)。例如下圖的一個(gè)二叉樹。如果當(dāng)前節(jié)點(diǎn)為1，則mostRight節(jié)點(diǎn)即為5；如果當(dāng)前節(jié)點(diǎn)為3，則mostRight節(jié)點(diǎn)即為6
實(shí)際上，Morris算法非常簡單。其基本遍歷流程如下：
將當(dāng)前節(jié)點(diǎn)cur初始化為root 當(dāng)前節(jié)點(diǎn)cur如果不存在左子樹。則將當(dāng)前節(jié)點(diǎn)指向其右子樹，以便遍歷當(dāng)前節(jié)點(diǎn)的右子樹 當(dāng)前節(jié)點(diǎn)cur如果存在左子樹，則先獲取cur節(jié)點(diǎn)的mostRight節(jié)點(diǎn) 如果mostRight節(jié)點(diǎn)的右子節(jié)點(diǎn)為空，此時(shí)說明cur節(jié)點(diǎn)的左子樹還未遍歷。故：一方面，我們將mostRight節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)置為cur節(jié)點(diǎn)；另一方面，將當(dāng)前節(jié)點(diǎn)指向其左子樹，以便遍歷當(dāng)前節(jié)點(diǎn)的左子樹 如果mostRight節(jié)點(diǎn)的右子節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)cur，此時(shí)說明cur節(jié)點(diǎn)的左子樹已經(jīng)遍歷完成。故：一方面，我們將mostRight節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)置為null空指針；另一方面，將當(dāng)前節(jié)點(diǎn)指向其右子樹，以便遍歷當(dāng)前節(jié)點(diǎn)的右子樹 重復(fù)Step 2、Step 3，直到當(dāng)前節(jié)點(diǎn)cur為null時(shí)為止
該算法遍歷過程的示意圖如下，可以看到當(dāng)一個(gè)節(jié)點(diǎn)的左子樹未遍歷完時(shí)，Morris算法會(huì)利用原葉子節(jié)點(diǎn)的null空指針修改樹。而當(dāng)該節(jié)點(diǎn)的左子樹遍歷后，會(huì)把對(duì)樹的修改進(jìn)行撤回。以恢復(fù)樹原有的結(jié)構(gòu)
前序遍歷
這里基于Morris算法來實(shí)現(xiàn)前序遍歷。問題的關(guān)鍵就在于何時(shí)對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行處理。顯然這里有兩個(gè)時(shí)機(jī)，一方面，遍歷過程中發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)的左子樹為空。則在對(duì)當(dāng)前節(jié)點(diǎn)的右子樹進(jìn)行遍歷前，需要對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行處理；另一方面，遍歷過程中發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)的左子樹不為空，則在對(duì)當(dāng)前節(jié)點(diǎn)的左子樹進(jìn)行遍歷前，需要對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行處理
/**
* 基于Morris算法的前序遍歷
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if( root == null ) {
return res;
}
TreeNode cur = root;
// 當(dāng)前節(jié)點(diǎn)cur的左子樹的最右節(jié)點(diǎn)
TreeNode mostRight = null;
while ( cur != null ) {
// 當(dāng)前節(jié)點(diǎn)的左子樹為空
if( cur.left == null ) {
// 處理當(dāng)前節(jié)點(diǎn)
res.add( cur.val );
// 處理當(dāng)前節(jié)點(diǎn)的右子樹
cur = cur.right;
} else { // 當(dāng)前節(jié)點(diǎn)的左子樹不為空
// 尋找當(dāng)前節(jié)點(diǎn)cur的左子樹的最右節(jié)點(diǎn)
mostRight = cur.left;
while ( mostRight.right!=null && mostRight.right!=cur ) {
mostRight = mostRight.right;
}
if( mostRight.right == null) { // 說明cur節(jié)點(diǎn)的左子樹未遍歷
// 處理當(dāng)前節(jié)點(diǎn)
res.add( cur.val );
// 處理當(dāng)前節(jié)點(diǎn)的左子樹
mostRight.right = cur;
cur = cur.left;
} else if ( mostRight.right == cur ) { // 說明cur節(jié)點(diǎn)的左子樹已經(jīng)遍歷完成
// 處理當(dāng)前節(jié)點(diǎn)的右子樹
mostRight.right = null;
cur = cur.right;
}
}
}
return res;
}
}
中序遍歷
這里基于Morris算法來實(shí)現(xiàn)中序遍歷。問題的關(guān)鍵就在于何時(shí)對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行處理。顯然這里有兩個(gè)時(shí)機(jī)，一方面，遍歷過程中發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)的左子樹為空。則在對(duì)當(dāng)前節(jié)點(diǎn)的右子樹進(jìn)行遍歷前，需要對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行處理；另一方面，遍歷過程中發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)的左子樹不為空，則在對(duì)當(dāng)前節(jié)點(diǎn)的左子樹完成遍歷后，需要對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行處理
/**
* 基于Morris算法的中序遍歷
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if( root == null ) {
return res;
}
TreeNode cur = root;
// 當(dāng)前節(jié)點(diǎn)cur的左子樹的最右節(jié)點(diǎn)
TreeNode mostRight = null;
while ( cur != null ) {
// 當(dāng)前節(jié)點(diǎn)的左子樹為空
if( cur.left == null ) {
// 處理當(dāng)前節(jié)點(diǎn)
res.add( cur.val );
// 處理當(dāng)前節(jié)點(diǎn)的右子樹
cur = cur.right;
} else { // 當(dāng)前節(jié)點(diǎn)的左子樹不為空
// 尋找當(dāng)前節(jié)點(diǎn)cur的左子樹的最右節(jié)點(diǎn)
mostRight = cur.left;
while ( mostRight.right!=null && mostRight.right!=cur ) {
mostRight = mostRight.right;
}
if( mostRight.right == null) { // 說明cur節(jié)點(diǎn)的左子樹未遍歷
// 處理當(dāng)前節(jié)點(diǎn)的左子樹
mostRight.right = cur;
cur = cur.left;
} else if ( mostRight.right == cur ) { // 說明cur節(jié)點(diǎn)的左子樹已經(jīng)遍歷完成
// 處理當(dāng)前節(jié)點(diǎn)
res.add( cur.val );
// 處理當(dāng)前節(jié)點(diǎn)的右子樹
mostRight.right = null;
cur = cur.right;
}
}
}
return res;
}
}
Note
這里給出本文中關(guān)于樹節(jié)點(diǎn)的類定義
/**
* 樹的節(jié)點(diǎn)
*/
class TreeNode {
TreeNode left;
TreeNode right;
int val;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}