遞歸模闆解決二叉樹的前中後序周遊問題

題目描述

二叉樹的前中後序周遊，是面試中的常考題目也是解決二叉樹問題的核心基礎，本次我們來介紹下如何通過遞歸的方式，求解這類問題，解決這類問題的思路包括使用遞歸或者疊代，本次我們主要介紹如何使用遞歸模闆來解決這類問題，通過使用模闆這三種周遊隻需進行細微的改動，即可得到最終的結果。

前中後相對的是誰？

二叉樹的前中後序周遊，指的是根節點所在的位置。

• 前序周遊

根 -> 左 -> 右

• 中序周遊

左 -> 根 -> 右

• 後序周遊

左 -> 右 -> 根

解題模闆

前序周遊，隻需要将處理函數放到1号位置，中序周遊隻需要将處理函數放到2号位置，後序周遊隻需要将處理函數放到3号位置上即可。

var postorderTraversal = function(root) {
  const result = [];
  function lastOrder(node) {
    if (!node) return 
    // 1号位置
    lastOrder(node.left);
    // 2号位置
    lastOrder(node.right);
    // 3号位置
    result.push(node.val);
  }
  lastOrder(root);
  return result;
};
複制代碼      

題目反思

二叉樹的前中後序周遊的遞歸解法，可以通過在函數中嵌套函數的方式來解決，所謂的前中後序周遊主要是處理函數放置的位置不同。