递归模板解决二叉树的前中后序遍历问题

题目描述

二叉树的前中后序遍历，是面试中的常考题目也是解决二叉树问题的核心基础，本次我们来介绍下如何通过递归的方式，求解这类问题，解决这类问题的思路包括使用递归或者迭代，本次我们主要介绍如何使用递归模板来解决这类问题，通过使用模板这三种遍历只需进行细微的改动，即可得到最终的结果。

前中后相对的是谁？

二叉树的前中后序遍历，指的是根节点所在的位置。

• 前序遍历

根 -> 左 -> 右

• 中序遍历

左 -> 根 -> 右

• 后序遍历

左 -> 右 -> 根

解题模板

前序遍历，只需要将处理函数放到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;
};
复制代码

题目反思

二叉树的前中后序遍历的递归解法，可以通过在函数中嵌套函数的方式来解决，所谓的前中后序遍历主要是处理函数放置的位置不同。