中序遍历

递归法中序遍历二叉树

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

迭代法中序遍历二叉树

1. 创建一个空栈 stack
2. 声明变量 current，初始值为根节点 root
3. 将 current 推入栈中，并且设置 current 为 current.left 直到 current 为 null
4. 如果 current 为 null，并且栈不为空，那么执行下列操作：
   1. 从栈中弹出顶部元素
   2. 处理弹出的元素，设置 current 为 弹出元素的右子树
   3. 继续第三步
5. 如果 current 为 null，并且栈为空，操作结束。

function iterativeInorder(root) {
  const result = [];
  const stack = [];
  let current = root;
  while (current !== null || stack.length > 0) {
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }
    // 执行到这里时, 通过两个 while 的条件确保 current 一定为 null, stack 一定不为空，
    current = stack.pop();
    result.push(current.val);
    current = current.right;
  }
  return result;
}

Test Cases

  /* Constructed binary tree is
                1
              /   \
            2      3
          /  \
        4     5
  */

const {
  recursiveInorder,
  iterativeInorder,
} = require('../docs/algo/tree/inorder');
const { generateTree } = require('../docs/algo/common/generator');

describe('inorder', () => {
  it('recursive', () => {
    const root = generateTree();
    expect(recursiveInorder(root)).toEqual([4, 2, 5, 1, 3]);
  });
  it('iterative', () => {
    const root = generateTree();
    expect(iterativeInorder(root)).toEqual([4, 2, 5, 1, 3]);
  });
});

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