二叉搜索樹的Morris中序遍歷(O(1)空間)思路

Achilles 發(fā)布于2019-08-23 14:36 / 1068人閱讀

摘要：關于二叉樹的遍歷，使用棧遞歸或者仿棧循環(huán)都是需要的空間，保證了空間為，時間還是比原來多了一遍。思路對每一個節(jié)點，優(yōu)先找到一個節(jié)點，這個節(jié)點的作用是，當后續(xù)節(jié)點遍歷到這個位置時，可以直接通過這個節(jié)點返回它需要返回的位置。

關于二叉樹的遍歷，使用棧遞歸或者仿棧循環(huán)都是需要O(N)的空間，Morris Traversal保證了空間為O(1)，時間還是O(N)（比原來多了一遍）。

這里只介紹inOrder順序。

思路：

對每一個cur節(jié)點，優(yōu)先找到一個pre節(jié)點，這個pre節(jié)點的作用是，當后續(xù)cur節(jié)點遍歷到這個位置時，可以直接通過這個pre節(jié)點返回它需要返回的位置。

例如：

上面當cur節(jié)點在6的時候，pre節(jié)點會在5，因為后面當cur節(jié)點遍歷到5的時候，可以通過pre節(jié)點直接返回6

當cur節(jié)點再4的時候，pre節(jié)點會在2，當后面cur到2的時候，可以直接返回4

pre找到了，是通過什么返回呢，因為不能修改二叉樹結(jié)構(gòu)，也不能使用堆棧記錄。

通過mirror(鏡像)，也就是說，當找到pre的時候（每個pre的右節(jié)點確保為null），在它的右節(jié)點創(chuàng)建一個鏡像節(jié)點，
這個鏡像節(jié)點直接指向當前的cur節(jié)點。

這個操作是不占用空間的，因為只是互相引用。

例如：當上面的cur為6，pre為5，那么設置pre.right=cur，感覺上是這樣：

其實并沒有多出來那一塊，只是5引用到6罷了

理解了這些，那么后續(xù)就簡單了，當cur遍歷到pre的時候并且打印后，將pre新增的引用刪除恢復原來的樹便可。

代碼：

function morrisTraversal(root){
  let cur=root,pre
  while(cur!=null){
    // 當左為空，直接打印
    if(cur.left==null){
      console.log(cur.val)
      cur=cur.right
    }else{
      // 當左不為空，先去找 pre
      pre=cur.left
      while(pre.right!=null && pre.right!==cur){
        pre=pre.right
      }
      // 建立引用，用于返回
      if(pre.right==null){
        pre.right=cur
        cur=cur.left
      }else{
        // 刪除引用
        console.log(cur.val)
        pre.right=null
        cur=cur.right
      }
    }
  }
}

GPU云服務器云服務器二叉樹的遍歷二叉樹的存儲二叉樹的存儲結(jié)構(gòu) java二叉樹的構(gòu)建

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/100846.html

樹和樹的算法

摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時間復雜度額外空間復雜度的二叉樹的遍歷方式，為二叉樹的節(jié)點個數(shù)。樹和樹的算法一、樹 1.1 樹的概念樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個有限節(jié)點組成一個...

RaoMeng 2019-08-19 11:08 評論0 收藏0
樹和樹的算法

摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時間復雜度額外空間復雜度的二叉樹的遍歷方式，為二叉樹的節(jié)點個數(shù)。樹和樹的算法一、樹 1.1 樹的概念樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個有限節(jié)點組成一個...

PiscesYE 2019-07-30 17:45 評論0 收藏0
【遞歸+迭代詳解】二叉樹的morris遍歷、層序遍歷、前序遍歷、中序遍歷、后序遍歷

摘要：遞歸解法由于層次遍歷的遞歸解法不是主流，因此只介紹前三種的遞歸解法前序遍歷遞歸遞歸中序遍歷遞歸遞歸后序遍歷遞歸遞歸三種遞歸遍歷的總結(jié)遞歸終止的條件為碰到空節(jié)點。目錄分析二叉樹的前序，中序，后序的遍歷步驟 1.層序遍歷方法一：廣度優(yōu)先搜索? (以下解釋來自leetcode官方題解) 方法...

niceforbear 2021-11-16 11:45 評論0 收藏0
【LeetCode 二叉樹專項】把二叉搜索樹轉(zhuǎn)換為累加樹（538）

摘要：解法一中序遍歷分析由于給定了二叉搜索樹，因此首先考慮中序遍歷，使用示例，我們先來分別看一下二叉搜索樹和累加樹中序遍歷的結(jié)果二叉搜索樹二叉累加樹。這里還是使用示例，我們再來觀察一下二叉搜索樹和累加樹中序遍歷的結(jié)果二叉搜索樹二叉累加樹。 ...

xcold 2021-11-18 10:02 評論0 收藏0
JS中的二叉樹遍歷

摘要：一個二叉樹的例子廣度優(yōu)先遍歷廣度優(yōu)先遍歷是從二叉樹的第一層根結(jié)點開始，自上至下逐層遍歷在同一層中，按照從左到右的順序?qū)Y(jié)點逐一訪問。有的書里將二叉樹的遍歷只講了上面三種遞歸遍歷。二叉樹是由根節(jié)點，左子樹，右子樹組成，左子樹和友子樹分別是一個二叉樹。這篇文章主要在JS中實現(xiàn)二叉樹的遍歷。一個二叉樹的例子 var tree = { value: 1, left: { ...

ghnor 2019-08-19 17:52 評論0 收藏0