先序遍历

递归法先序遍历二叉树

function recursivePreorder(root) {
  const result = [];
  function traverse(node) {
    if (node === null) {
      return;
    }
    result.push(node.val);
    traverse(node.left);
    traverse(node.right);
  }
  traverse(root);
  return result;
}

迭代法先序遍历二叉树

1. 创建一个空的栈
2. 放入 root 节点到栈中
3. 当栈不为空时执行下列操作：
   1. 从栈中弹出顶部节点，并进行处理
   2. 将弹出节点的右子树加入栈中
   3. 将弹出节点的左子树加入栈中

注意：先将右子树入栈，从而确保左子树先被处理

function iterativePreorder(root) {
  // Base condition
  if (root === null) return [];
  const result = [];
  const stack = [];
  stack.push(root);
  while (stack.length > 0) {
    const node = stack[stack.length - 1];
    result.push(node.val);
    stack.pop();
    if (node.right !== null) {
      stack.push(node.right);
    }
    if (node.left !== null) {
      stack.push(node.left);
    }
  }
  return result;
}

Test Cases

const {
  recursivePreorder,
  iterativePreorder,
} = require('../docs/algo/tree/preorder');

describe('traverse', () => {
  it('preorder', () => {
    class Node {
      constructor(val) {
        this.val = val || 0;
        this.left = null;
        this.right = null;
      }
    }
    const root = new Node(1);
    const two = new Node(2);
    const three = new Node(3);
    root.left = two;
    root.right = three;
    two.left = new Node(4);
    two.right = new Node(5);
    three.left = new Node(6);
    const result1 = recursivePreorder(root);
    const result2 = iterativePreorder(root);
    expect(result1).toEqual([1, 2, 4, 5, 3, 6]);
    expect(result2).toEqual([1, 2, 4, 5, 3, 6]);
  });
});

# /test/preorder.test.js
jest --testNamePattern=preorder

递归法先序遍历 N 叉树

function preorderNAryTree(root) {
  const result = []
  function helper(node) {
    if (node === null) {
      return;
    }
    result.push(node.val)
    for (const child of node.children) {
      helper(child)
    }
  }
  helper(root)
  return result
}