编写一个函数，实现二叉树的遍历（前序、中序、后序）

推荐答案

// www.javascriptcn.com code example
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = this.right = null;
  }
}

// 前序遍历
function preorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (!node) return;
    result.push(node.val); // 访问根节点
    traverse(node.left);   // 遍历左子树
    traverse(node.right);  // 遍历右子树
  }
  traverse(root);
  return result;
}

// 中序遍历
function inorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (!node) return;
    traverse(node.left);   // 遍历左子树
    result.push(node.val); // 访问根节点
    traverse(node.right);  // 遍历右子树
  }
  traverse(root);
  return result;
}

// 后序遍历
function postorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (!node) return;
    traverse(node.left);   // 遍历左子树
    traverse(node.right);  // 遍历右子树
    result.push(node.val); // 访问根节点
  }
  traverse(root);
  return result;
}

本题详细解读

1. 二叉树遍历的基本概念

二叉树的遍历是指按照某种顺序访问树中的所有节点。常见的遍历方式有三种：

• 前序遍历：先访问根节点，然后遍历左子树，最后遍历右子树。
• 中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树。
• 后序遍历：先遍历左子树，然后遍历右子树，最后访问根节点。

2. 代码实现解析

• TreeNode类：首先定义了一个TreeNode类，用于表示二叉树的节点。每个节点包含一个值val，以及指向左子树和右子树的指针left和right。

• 前序遍历：

  • 使用递归的方式实现前序遍历。
  • 首先访问根节点，将其值加入结果数组result。
  • 然后递归遍历左子树和右子树。

• 中序遍历：

  • 同样使用递归的方式实现中序遍历。
  • 首先递归遍历左子树。
  • 然后访问根节点，将其值加入结果数组result。
  • 最后递归遍历右子树。

• 后序遍历：

  • 使用递归的方式实现后序遍历。
  • 首先递归遍历左子树和右子树。
  • 最后访问根节点，将其值加入结果数组result。

3. 递归与迭代的选择

• 递归：递归实现简单直观，适合理解遍历的基本思想。但在实际应用中，递归可能会导致栈溢出问题，尤其是在树非常深的情况下。
• 迭代：迭代实现通常使用栈来模拟递归过程，避免了栈溢出的问题。但在代码实现上相对复杂一些。

4. 时间复杂度与空间复杂度

• 时间复杂度：三种遍历方式的时间复杂度均为O(n)，其中n为二叉树的节点数，因为每个节点都会被访问一次。
• 空间复杂度：递归实现的空间复杂度为O(h)，其中h为二叉树的高度。最坏情况下，二叉树退化为链表，空间复杂度为O(n)。