二叉树遍历方法总结二叉树遍历方法总结

深度优先遍历 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; }