二叉树遍历

问题

实现二叉树遍历：前序、中序和后序。

解答

树节点定义

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

前序遍历（根 → 左 → 右）

function preorder(root) {
  const result = [];
  
  function traverse(node) {
    if (!node) return;
    result.push(node.val);  // 访问根
    traverse(node.left);     // 访问左子树
    traverse(node.right);    // 访问右子树
  }
  
  traverse(root);
  return result;
}

中序遍历（左 → 根 → 右）

function inorder(root) {
  const result = [];
  
  function traverse(node) {
    if (!node) return;
    traverse(node.left);     // 访问左子树
    result.push(node.val);   // 访问根
    traverse(node.right);    // 访问右子树
  }
  
  traverse(root);
  return result;
}

后序遍历（左 → 右 → 根）

function postorder(root) {
  const result = [];
  
  function traverse(node) {
    if (!node) return;
    traverse(node.left);     // 访问左子树
    traverse(node.right);    // 访问右子树
    result.push(node.val);   // 访问根
  }
  
  traverse(root);
  return result;
}

关键点

• 记住顺序：前序（根在前）、中序（根在中）、后序（根在后）
• 二叉搜索树的中序遍历得到有序序列
• 也可以使用栈实现迭代版本