数据

{
  "value": 1,
  "left": {
    "value": 2,
    "left": {
      "value": 4,
      "left": null,
      "right": null
    },
    "right": {
      "value": 5,
      "left": null,
      "right": null
    }
  },
  "right": {
    "value": 3,
    "left": {
      "value": 6,
      "left": null,
      "right": null
    },
    "right": {
      "value": 7,
      "left": null,
      "right": null
    }
  }
}

遍历二叉树

深度优先遍历(包括前序、中序、后序遍历)

前序

先访问根节点，然后访问左子树，最后访问右子树：

function foreachTree(tree) {
  if(!tree) return
  console.log(tree.value)
  foreachTree(tree.left)
  foreachTree(tree.right)
}

function foreachTree(tree) {
  if(!tree) return
  const stack = [tree];
  while(stack.length > 0) {
    const node = stack.pop();
    console.log(node.value);
    if(node.right) {
      stack.push(node.right);
    }
    if(node.left) {
      stack.push(node.left);
    }
  }
}

中序

先访问左子树，然后访问根节点，最后访问右子树：

function foreachTree(tree) {
  if(!tree) return
  foreachTree(tree.left)
  console.log(tree.value)
  foreachTree(tree.right)
}

function inorderTraversalIterative(root) {
    const stack = [];
    let current = root;
    while (current || stack.length > 0) {
        // 不断将当前节点及其左子节点压入栈中
        while (current) {
            stack.push(current);
            current = current.left;
        }
        // 从栈中弹出一个节点并访问
        current = stack.pop();
        console.log(current.value)
        // 将当前节点更新为弹出节点的右子节点
        current = current.right;
    }
}

后序

先访问左子树，然后访问右子树，最后访问根节点：

function foreachTree(tree) {
  if(!tree) return
  foreachTree(tree.left)
  foreachTree(tree.right)
  console.log(tree.value)
}

function postorderTraversalIterative(root) {
  if (!root) return;
  const stack1 = [root];
  const stack2 = []; // 用于存储反向的结果

  while (stack1.length) {
    const node = stack1.pop();
    stack2.push(node); // 将节点压入辅助栈
    if (node.left) stack1.push(node.left); // 左子节点先入主栈
    if (node.right) stack1.push(node.right); // 右子节点后入主栈
  }

  // 依次输出辅助栈内容（反转）
  while (stack2.length) {
    const node = stack2.pop();
    console.log(node.value); // 访问当前节点
  }
}

广度优先遍历(层级遍历)

按层从上到下依次访问节点。

function breadthFirstTraversal(root) {
    if (!root) return;

    const queue = [root]; // 初始化队列，将根节点放入队列

    while (queue.length > 0) {
        const currentNode = queue.shift(); // 从队列中取出当前节点
        console.log(currentNode.value); // 输出当前节点的值

        // 将当前节点的左子节点和右子节点放入队列
        if (currentNode.left) {
            queue.push(currentNode.left);
        }
        if (currentNode.right) {
            queue.push(currentNode.right);
        }
    }
}