Tree traversal

Here is a summary of a few common implementations of tree traversals.

In order traversal

# recursive
def dfs(root):
  if not root:
    return
  dfs(root.left)
  visit(root)
  dfs(root.right)
  return

# iterative
def inorder(root):
  stack = []
  node = root
  while node or stack:
    if node:
      stack.append(node)
      node = node.left
    else:
      node = stack.pop()
      visit(node)
      node = node.right

pre order

# recursive
def dfs(root):
  if not root:
    return
  visit(root)
  dfs(root.left)
  dfs(root.right)

# iterative 1
def preorder(root):
  stack = [root]
  while stack:
    node = stack.pop()
    visit(node)
    if node.right:
      stack.append(node.right)
    if node.left:
      stack.append(node.left)

# iterative 2
def preorder(root):
  stack = []
  node = root
  while node or stack:
    if node:
      stack.append(node)
      visit(node)
      node = node.left
    else:
      node = stack.pop()
      node = node.right

post order

# recursive
def dfs(root):
  if not root:
    return
  dfs(root.left)
  dfs(root.right)
  visit(root)
  return

# iterative only visit a node when we know its right child (if exist) has been visited before.
def postorder(root):
  last = None
  stack = []
  node = root
  while node or stack:
    if node:
      stack.append(node)
      node = node.left
    else:
      top = stack[-1]
      # its right node has not been visited
      if top.right and top.right != last:
        node = top.right
        stack.append(node)
      else:
        last = top
        visit(top)

# post order = reverse of (pre order (root, right, left))
# code ommitted as an exercise. See discussion 1 for answer.

Reference

discussion 1
discussion 2

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末液南,一起剝皮案震驚了整個濱河市映跟,隨后出現(xiàn)的幾起案子镇草,更是在濱河造成了極大的恐慌,老刑警劉巖,帶你破解...
    沈念sama閱讀 223,126評論 6 520
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異亭病,居然都是意外死亡,警方通過查閱死者的電腦和手機嘶居,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,421評論 3 400
  • 文/潘曉璐 我一進店門罪帖,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人邮屁,你說我怎么就攤上這事整袁。” “怎么了佑吝?”我有些...
    開封第一講書人閱讀 169,941評論 0 366
  • 文/不壞的土叔 我叫張陵坐昙,是天一觀的道長。 經常有香客問我芋忿,道長炸客,這世上最難降的妖魔是什么疾棵? 我笑而不...
    開封第一講書人閱讀 60,294評論 1 300
  • 正文 為了忘掉前任巾乳,我火速辦了婚禮膳沽,結果婚禮上糊渊,老公的妹妹穿的比我還像新娘柒爵。我一直安慰自己,他們只是感情好膝蜈,可當我...
    茶點故事閱讀 69,295評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著,像睡著了一般抖所。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上痕囱,一...
    開封第一講書人閱讀 52,874評論 1 314
  • 那天田轧,我揣著相機與錄音,去河邊找鬼鞍恢。 笑死傻粘,一個胖子當著我的面吹牛,可吹牛的內容都是我干的帮掉。 我是一名探鬼主播弦悉,決...
    沈念sama閱讀 41,285評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼蟆炊!你這毒婦竟也來了稽莉?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 40,249評論 0 277
  • 序言:老撾萬榮一對情侶失蹤涩搓,失蹤者是張志新(化名)和其女友劉穎污秆,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體昧甘,經...
    沈念sama閱讀 46,760評論 1 321
  • 正文 獨居荒郊野嶺守林人離奇死亡良拼,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,840評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了充边。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片庸推。...
    茶點故事閱讀 40,973評論 1 354
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖浇冰,靈堂內的尸體忽然破棺而出予弧,到底是詐尸還是另有隱情,我是刑警寧澤湖饱,帶...
    沈念sama閱讀 36,631評論 5 351
  • 正文 年R本政府宣布掖蛤,位于F島的核電站,受9級特大地震影響井厌,放射性物質發(fā)生泄漏蚓庭。R本人自食惡果不足惜致讥,卻給世界環(huán)境...
    茶點故事閱讀 42,315評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望器赞。 院中可真熱鬧垢袱,春花似錦、人聲如沸港柜。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,797評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽夏醉。三九已至爽锥,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間畔柔,已是汗流浹背氯夷。 一陣腳步聲響...
    開封第一講書人閱讀 33,926評論 1 275
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留靶擦,地道東北人腮考。 一個月前我還...
    沈念sama閱讀 49,431評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像玄捕,于是被迫代替她去往敵國和親踩蔚。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,982評論 2 361

推薦閱讀更多精彩內容