深度优先遍历
1) 前序遍历
递归实现：
const preOrder = (root) => { let result = []; const traverseNode = (node) => { if (node) { // 先根节点 result.push(node.val); // 而后遍历左子树 traverseNode(node.left); // 再遍历右子树 traverseNode(node.right); } } traverseNode(root); return result;}非递归实现：
const preOrder = (root) => { let list = []; let stack = []; // 当根节点不为空的时候，将根节点入栈 if (root != null) stack.push(root); while (stack.length > 0) { root = stack.pop(); // 先拜访根节点 list.push(root.val); // 咱们先打印左子树，而后右子树 // 所以先入栈的是右子树，而后左子树 if (root.right != null) stack.push(root.right); if (root.left != null) stack.push(root.left); } return list;}2) 中序遍历
递归实现：
const inOrder = (root) => { let result = []; const traverseNode = (node) => { if (node) { // 先遍历左子树 traverseNode(node.left); // 而后根节点 result.push(node.val); // 再遍历右子树 traverseNode(node.right); } } traverseNode(root); return result;}非递归实现：
const inOrder = (root) => { let list = []; let stack = []; while (stack.length > 0 || root != null) { if (root != null) { // 如果以后节点非空，就将以后节点入栈 stack.push(root); // 指针向以后节点的左节点方向挪动 root = root.left; } else { // 以后节点为空，则从栈顶弹出元素 root = stack.pop(); list.push(root.val); // 指针向右节点方向挪动 root = root.right; } } return list;}3) 后序遍历
递归实现：
const postOrder = (root) => { let result = []; const traverseNode = (node) => { if (node) { // 先遍历左子树 traverseNode(node.left); // 而后遍历右子树 traverseNode(node.right); // 最初根节点 result.push(node.val); } } traverseNode(root); return result;}非递归实现：
const postOrder = (root) => { let list = []; let stack = []; // 当根节点不为空，将根节点入栈 if (root != null) stack.push(root); while (stack.length > 0) { root = stack.pop(); // 因为后序遍历输入程序是：左=>右=>根 // 先将增加后果的程序反一下 list.unshift(root.val); // 而后让左子树先入栈，后右子树 // 这样出栈程序就变成先右后左 if (root.left != null) stack.push(root.left); if (root.right != null) stack.push(root.right); } return list;}