如何花最少的資源遍歷二叉樹-創(chuàng)新互聯(lián)

文章目錄
    • 一、遞歸遍歷二叉樹
      • 1.1 前序遍歷
      • 1.2 中序遍歷
      • 1.3 后序遍歷
    • 二、非遞歸遍歷二叉樹
      • 2.1 前序遍歷
      • 2.2 中序遍歷
      • 2.3 后序遍歷
    • 三、高效的 Morris 遍歷
      • 3.1 前序遍歷
      • 3.2 中序遍歷
      • 3.3 后序遍歷

關(guān)于二叉樹的遍歷也是面試過程中非常有可能考的話題。

常見的簡單的遞歸遍歷二叉樹，非常的基礎(chǔ)，顯而易見，這并不會是面試官想要的看的遍歷二叉樹的方法。一般來說，非遞歸實現(xiàn)二叉樹的遍歷才是考得相對較多的，時間復雜度 O（N），空間復雜度 O（N）

創(chuàng)新互聯(lián)是一家專業(yè)從事成都網(wǎng)站制作、做網(wǎng)站的網(wǎng)絡公司。作為專業(yè)網(wǎng)絡公司,創(chuàng)新互聯(lián)依托的技術(shù)實力、以及多年的網(wǎng)站運營經(jīng)驗,為您提供專業(yè)的成都網(wǎng)站建設、全網(wǎng)營銷推廣及網(wǎng)站設計開發(fā)服務！

如果我們能夠在空間復雜度為 O（1）的條件下實現(xiàn)二叉樹的遍歷，這將是一個很好的加分項，這就是文章后面介紹的Morris 遍歷
在這里插入圖片描述

那么接下來我們先回顧一下遞歸和非遞歸的方法遍歷二叉樹的做法，然后介紹 Morris 遍歷

二叉樹節(jié)點（TreeNode）

class TreeNode {int val = 0; //值
  TreeNode left = null;  //左節(jié)點
  TreeNode right = null;  //右節(jié)點
  public TreeNode(int val) {this.val = val;
  }
}
一、遞歸遍歷二叉樹

按照如圖所示進行二叉樹的遍歷，遍歷的節(jié)點順序如圖所示。

在這里插入圖片描述

我們會發(fā)現(xiàn)每個節(jié)點都會遍歷到三次，先序遍歷的結(jié)果就是節(jié)點被第一次遇見的順序，中序遍歷的結(jié)果就是節(jié)點被第二次遇見的順序，后序遍歷的結(jié)果就是節(jié)點被第三次遇見的順序

1.1 前序遍歷

前序遍歷二叉樹的順序是，根——》左——》右

basecase：

當節(jié)點 root 為null 時，即遇見了空節(jié)點，就可以直接返回了

遞歸過程：

獲取到一棵二叉樹后，但凡遇見的節(jié)點不是空節(jié)點，那么我們就將其放到結(jié)果列表中，然后分別遍歷該節(jié)點的左子樹和右子樹。那么對于子樹處理方式也是一樣的

public class Solution1 {public Listlist = new ArrayList<>(); //返回的結(jié)果列表
    public ListpreorderTraversal (TreeNode root) {if(root == null) {return list; 
        }
        func1(root);
        return list;
    }
    public void func1(TreeNode root) {if(root == null) {return;  //basecase
        }
        list.add(root.val);//添加到結(jié)果列表中
        func1(root.left); //遍歷左子樹
        func1(root.right);//遍歷右子樹
    }
}
1.2 中序遍歷

中序遍歷二叉樹的順序是，左——》根——》右

本質(zhì)上和前序遍歷的沒有什么不同，不過是寫在了同一個方法中

public class Solution2 {Listlist = new ArrayList<>();
    public ListinorderTraversal(TreeNode root) {if(root == null) 
            return list;
        inorderTraversal(root.left); //遍歷左子樹
        list.add(root.val);  //添加到結(jié)果列表中
        inorderTraversal(root.right); //遍歷右子樹
        return list; 
    }
}
1.3 后序遍歷

中序遍歷二叉樹的順序是，左——》右——》根

public class Solution3 {public ListpostorderTraversal(TreeNode root) {Listlist = new ArrayList<>();
        if(root == null) return list;
        
        ListleftTree = postorderTraversal(root.left);
        list.addAll(leftTree);//將左子樹的后序遍歷結(jié)果放到結(jié)果列表中

        ListrightTree = postorderTraversal(root.right);
        list.addAll(rightTree);//將右子樹的后序遍歷結(jié)果放到結(jié)果列表中

        list.add(root.val);
        //此時左子樹和右子樹后序遍歷的結(jié)果放好了，就將當前根節(jié)點值放到結(jié)果列表中
        return list;
    }
}
二、非遞歸遍歷二叉樹

非遞歸遍歷實際上將就是將壓棧這個步驟自己進行實現(xiàn)

2.1 前序遍歷

前序遍歷是 根、左、右 這樣的順序，那么就應該先把根節(jié)點入棧

在這里插入圖片描述

然后彈出一個節(jié)點，即當前的根節(jié)點，保存到結(jié)果列表 list 中。并且只要當前的根節(jié)點的左右節(jié)點不為空，就將他們壓入棧。先壓右節(jié)點，再壓左節(jié)點。因為棧是先進后出的，為了先處理左子樹，就應該讓左節(jié)點在右節(jié)點后入棧

在這里插入圖片描述

只要棧不為空，我們就繼續(xù)彈出一個節(jié)點，進行保存，當前彈出的是棧頂?shù)?B 節(jié)點，說明開始處理左子樹了

在這里插入圖片描述

等到下一輪 D 節(jié)點都彈出時，說明以 B 節(jié)點為根節(jié)點的子樹已經(jīng)處理完畢了，接下來要開始處理以 C 節(jié)點為根節(jié)點的子樹，依次類推，直到棧為空，循環(huán)結(jié)束

public class Solution1 {public ArrayListlist = new ArrayList<>();//結(jié)果列表
    public void func2(TreeNode root) {Stackstack = new Stack<>();
        stack.push(root);//先將根節(jié)點入棧
        //只要棧不為空就一直循環(huán)
        while (!stack.isEmpty()) {TreeNode cur = stack.pop();//彈出元素，當前的根
            list.add(cur.val);//保存
            //先壓右節(jié)點，再壓左節(jié)點
            if (cur.right != null) {stack.push(cur.right);
            }
            if (cur.left != null) {stack.push(cur.left);
            }
        }
    }
}
2.2 中序遍歷

中序遍歷的順序是 左、根、右

只要 root 節(jié)點不為空，就不斷的將其左子節(jié)點壓入棧中，root 在走到 root 的左節(jié)點上

在這里插入圖片描述

遇見空節(jié)點，那么該空節(jié)點必然是其父節(jié)點的左節(jié)點（左子樹處理完畢），此時從棧中彈出一個節(jié)點便是該子樹的根節(jié)點，進行保存。然后讓 root 走到方才彈出的根節(jié)點的右子樹上，繼續(xù)處理右子樹的內(nèi)容，處理的方式同上

在這里插入圖片描述

顯而易見，此時 root 為空，那么只要 root 不為空或者棧不為空循環(huán)都會繼續(xù)，繼續(xù)從棧中彈出節(jié)點，進行保存。

直到彈出節(jié)點 A，進行保存，此時棧為空了。但是 root 不為空，指向節(jié)點 A 的右子樹上的根節(jié)點 C 呢，循環(huán)繼續(xù)。也就是說，此時節(jié)點 A 的左子樹處理完畢，根處理完畢，開始處理右子樹。

以此類推，直到棧中沒有節(jié)點了，root 也為空了，一切就真的結(jié)束了

public class Solution2 {public ArrayListlist = new ArrayList<>();//結(jié)果列表
    public void func2(TreeNode root) {Stackstack = new Stack<>();
        while (root != null || !stack.isEmpty()) {//一股腦將左邊界都添加到棧中，直到遇見null
            while (root != null) {stack.push(root);
                root = root.left;
            }
            //此時的root為null了，彈出一個元素，走到其右子樹中
            TreeNode node = stack.pop();
            list.add(node.val);
            root = node.right;//對于右子樹的處理方法同上
        }
    }
}
2.3 后序遍歷

后序遍歷的思想和前序遍歷的思想非常的像。

已知后序遍歷的順序是 左、右、根。棧的特點就是先進后出，那么如果我們遍歷二叉樹以根、右、左 的順序使用一個收集棧保存節(jié)點，是可以做到的（模仿前序遍歷，區(qū)別就是先壓左節(jié)點再壓右節(jié)點）。

最后再將收集棧中的節(jié)點一個個彈出，就是左、右、根的順序

public class Solution3 {public ArrayListlist = new ArrayList<>();//結(jié)果列表
    public void func2(TreeNode root) {Stackstack1 = new Stack<>();//壓棧
        Stackstack2 = new Stack<>();//收集棧
        stack1.push(root);//先壓入根節(jié)點
        while (!stack1.isEmpty()) {TreeNode node = stack1.pop();//彈出一個元素,將其值放到收集棧中
            stack2.push(node.val);
            //方才彈出的元素，有左先壓左，有右再壓右
            if (node.left != null) {stack1.push(node.left);
            }
            if (node.right != null) {stack1.push(node.right);
            }
            //周而復始
        }
        //將收集棧中的元素倒出來
        //stack1的出棧順序是根右左，壓入到stack2中再彈出來，就是左右根
        while (!stack2.isEmpty()) {list.add(stack2.pop());
        }
    }
}
三、高效的 Morris 遍歷

在上面的遍歷方式中時間復雜度為 O（N），因為要遍歷每個節(jié)點?？臻g復雜度為 O（N），因為使用到了棧，無論是遞歸使用的系統(tǒng)的棧還是非遞歸自己手動創(chuàng)建的棧。

Morris 遍歷是一種和上面的遍歷方式不太一樣的遍歷方式，通過利用樹中的空節(jié)點，來達到節(jié)省空間的目的，空間復雜度為 O（1）

遍歷介紹：

有一個 TreeNode 類型的變量 cur 此時正在根節(jié)點處

  1. 如果 cur 節(jié)點沒有左孩子，cur 直接移動到右孩子上
  2. 如果 cur 節(jié)點有左孩子，那就找到左子樹上最右的節(jié)點 Rightmost
    • 若 Rightmost 節(jié)點的右指針指向空，那就讓右指針指向 cur，然后 cur 向左邊移動
    • 若 Rightmost 節(jié)點的右指針已經(jīng)指向 cur 了，那就讓它指向 null，然后cur 往右移
  3. cur 為空，遍歷結(jié)束

遍歷過程：

此時的 cur 指向 A 節(jié)點，有左孩子，且左子樹上的最右節(jié)點是 B 節(jié)點，那就讓 B 的右指針指向 cur，cur 往左子樹上移動

在這里插入圖片描述

發(fā)現(xiàn) cur 依舊有左孩子，按照之前的做法進行操作。cur 即將移動到其左孩子 D 節(jié)點上

在這里插入圖片描述

終于發(fā)現(xiàn) cur 沒有左孩子了，那就往其右子樹移動
在這里插入圖片描述

此時的 cur 沒有左孩子，cur 就往 G 節(jié)點的右子樹上移動，回到了 B 節(jié)點

在這里插入圖片描述

cur 回到 B 節(jié)點后，B 節(jié)點有左子樹，并且左子樹的最右節(jié)點 Rightmost 正指向 cur 呢，那就讓它給指回 null，恢復原樣，然后 cur 往其右孩子上移動

在這里插入圖片描述

cur 往 B 節(jié)點的右孩子移動，就又回到了 A 節(jié)點，A 節(jié)點有左子樹，并且左子樹的最右節(jié)點正指向 cur（A 節(jié)點）,就將其恢復原樣，重新指向 null，然后 cur 往其右孩子上移動

在這里插入圖片描述

這樣子一來，這個二叉樹的左子樹以及根節(jié)點算是遍歷完成了，接下來的右子樹也是同樣的規(guī)則進行遍歷

在這里插入圖片描述

直到 cur 為空，遍歷就算結(jié)束了

在這里插入圖片描述

我們可以發(fā)現(xiàn)，所有的擁有左子樹的節(jié)點都遍歷了兩次，其余的節(jié)點只遍歷了一次

代碼實現(xiàn)：

public class Solution5 {public static void Morris (TreeNode root) {if (root == null) {return;
        }
        TreeNode cur = root;
        TreeNode rightMost = null;
        while (cur != null) {rightMost = cur.left;//開始找左子樹中最右的節(jié)點
            if (rightMost == null) {//沒有左孩子
                cur = cur.right;
            }else {//有左孩子
                //先讓 rightMost 指向 cur 左子樹的最右節(jié)點
                while (rightMost.right != null && rightMost.right != cur) {rightMost = rightMost.right;
                }
                //到這里，rightMost 的 right 可能為 null，可能為 cur
                if (rightMost.right == cur) {//說明是第二遍到 cur 節(jié)點
                    rightMost.right = null;//讓其回歸正常
                    cur = cur.right;
                }else {//第一遍來到 cur 節(jié)點
                    rightMost.right = cur;
                    cur = cur.left;
                }
            }
        }
    }
}
3.1 前序遍歷

對于前序遍歷來說，如果某個節(jié)點沒有左孩子，只會遍歷到一次，就直接打印。如果有左孩子的，說明可以遍歷到兩次，那么第一次遍歷到的時候打印

在這里插入圖片描述

紅色部分就是前序遍歷的節(jié)點順序，和預期的一模一樣

public class Solution5 {public static void preMorris (TreeNode root) {if (root == null) {return;
        }
        TreeNode cur = root;
        TreeNode rightMost = null;
        while (cur != null) {rightMost = cur.left;
            if (rightMost == null) {System.out.println(cur.val);//唯一一次遍歷，打印
                cur = cur.right;
            }else {while (rightMost.right != null && rightMost.right !=cur) {rightMost = rightMost.right;
                }
                if (rightMost.right == cur) {//說明是第二遍到 cur 節(jié)點
                    rightMost.right = null;
                    cur = cur.right;
                }else {//第一遍來到 cur 節(jié)點
                    System.out.println(cur.val);//第一次出現(xiàn)，打印
                    rightMost.right = cur;
                    cur = cur.left;
                }
            }
        }
    }
}
3.2 中序遍歷

對于中序遍歷來說，如果某個節(jié)點沒有左孩子，只會遍歷到一次，就直接打印。如果有左孩子的，說明可以遍歷到兩次，那么第二次遍歷到的時候打印

在這里插入圖片描述

public class Solution5 {public static void inMorris (TreeNode root) {if (root == null) {return;
        }
        TreeNode cur = root;
        TreeNode rightMost = null;
        while (cur != null) {rightMost = cur.left;
            if (rightMost == null) {System.out.println(cur.val);//唯一一次遍歷，打印
                cur = cur.right;
            }else {while (rightMost.right != null && rightMost.right !=cur) {rightMost = rightMost.right;
                }
                if (rightMost.right == cur) {//說明是第二遍到 cur 節(jié)點
                    System.out.println(cur.val);//第二次出現(xiàn)，打印
                    rightMost.right = null;
                    cur = cur.right;
                }else {//第一遍來到 cur 節(jié)點
                    rightMost.right = cur;
                    cur = cur.left;
                }
            }
        }
    }
}
3.3 后序遍歷

對于后序遍歷來說，如果某個節(jié)點沒有左孩子，那就不管了。

如果有左孩子并且是第二次到達該節(jié)點，那么就將該節(jié)點的左子樹的右邊界逆序打印。

一切完成之后，將整棵樹的右邊界進行逆序打印

在這里插入圖片描述

在這里插入圖片描述

如圖所示，在 Morris 遍歷中， A 和 B 是擁有左子樹的節(jié)點且是第一次遍歷，跳過。D 和 G 都沒有左子樹，跳過。

又遍歷到了 B 節(jié)點，這是第二次遍歷到 B 節(jié)點，并且 B 節(jié)點還是第二次遍歷到，所以就逆序打印 B 節(jié)點左子樹的右邊界 G D，后面的節(jié)點就依次根據(jù)這些內(nèi)容來判斷。

直到遍歷完全之后，逆序打印整棵樹的右邊界

注：在第二遍遍歷到該節(jié)點的時候，需要先進行還原二叉樹，即將對應的 Rightmost 的 right 指向 null，然后在進行逆序打印右邊界操作

public static void postMorris (TreeNode root) {if (root == null) {return;
    }
    TreeNode cur = root;
    TreeNode rightMost = null;
    while (cur != null) {rightMost = cur.left;//開始找左子樹中最右的節(jié)點
        if (rightMost == null) {//沒有左孩子
            cur = cur.right;
        }else {//有左孩子
            while (rightMost.right != null && rightMost.right !=cur) {rightMost = rightMost.right;
            }
            if (rightMost.right == cur) {//說明是第二遍到 cur 節(jié)點
                rightMost.right = null;//先讓其回歸正常
                printFunc(cur.left);//逆序打印
                cur = cur.right;
            }else {//第一遍來到 cur 節(jié)點
                rightMost.right = cur;
                cur = cur.left;
            }
        }
    }
    printFunc(root);//最后總的逆序打印整棵樹的右邊界
}
//提供了一個樹的根節(jié)點，逆序打印這棵樹的右邊界
public static void printFunc(TreeNode root) {TreeNode tail = reverseRightEdge(root);
    TreeNode cur = tail;//進行一個反轉(zhuǎn)
    while (cur != null) {System.out.println(cur.val);
        cur = cur.right;
    }
    reverseRightEdge(tail);//給它反轉(zhuǎn)回去
}
//反轉(zhuǎn)右邊界(類似于反轉(zhuǎn)單鏈表)
public static TreeNode reverseRightEdge(TreeNode root) {TreeNode cur = root;
    TreeNode prev = null;
    while (cur != null) {TreeNode curNext = cur.right;
        cur.right = prev;
        prev = cur;
        cur = curNext;
    }
    return prev;
}

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站題目：如何花最少的資源遍歷二叉樹-創(chuàng)新互聯(lián)
瀏覽地址：http://muchs.cn/article32/djgspc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、做網(wǎng)站、品牌網(wǎng)站設計、微信公眾號、云服務器、手機網(wǎng)站建設

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

網(wǎng)站托管運營