中序遍历

中序遍历（In-Order Traversal）先操作左子树，再操作根节点，最后操作右子树

算法

递归

const inOrderTraversal = (root) => {
	if (!root) return [];
	const res = [];
	const inOrderRecursion = (node) => {
		if (node.left) inOrderRecursion(node.left);
		res.push(node.val);
		if (node.right) inOrderRecursion(node.right);
	};
	inOrderRecursion(root);
	return res;
};

迭代

中序遍历的迭代使用栈stack来保存将要遍历的节点

从根节点开始：如果当前节点存在，将当前节点压入栈，然后将该节点的左孩子当作新的根节点；如果当前节点不存在，则弹出栈顶节点，将弹出的节点的值保存在结果数组中，并且将该节点的右孩子当作新的根节点继续判断

迭代直到当前节点不存在或者栈stack为空时停止

const inOrderTraversal = (root) => {
	if (!root) return [];
	const res = [];
	const stack = [];
	while (stack.length || root) {
		if (root) {
			stack.push(root);
			root = root.left;
		} else {
			root = stack.pop();
			res.push(root.val);
			root = root.right;
		}
	}
	return res;
};