目录
一、前序遍历
（1）递归实现
首先我们需要了解什么是二叉树的前序遍历：按照访问根节点——左子树——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
let result=[]
const dfs=function(root){
if(root===null) return;
result.push(root.val)
dfs(root.left)
dfs(root.right)
}
dfs(root)
return result
};（2）迭代实现
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
if(!root) return []
let res=[],stack=[]
stack.push(root)
while(stack.length){
const cur=stack.pop()
res.push(cur.val)
//栈的特性先进后出，所以先存右孩子
if(cur.right) stack.push(cur.right)
if(cur.left) stack.push(cur.left)
}
return res
};二、中序遍历??
按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。
（1）递归实现
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
let result=[]
const dfs=function(root){
if(root===null) return;
dfs(root.left)
result.push(root.val)
dfs(root.right)
}
dfs(root)
return result
};（2） 迭代实现
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
if(!root) return []
const res=[],stack=[]
let cur=root
while(cur||stack.length){
while(cur){
stack.push(cur)
cur=cur.left
}
const node=stack.pop()
res.push(node.val)
cur=node.right
}
return res
};三、后序遍历
按照访问左子树——右子树——根节点的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。
（1）递归实现
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
let result=[]
const dfs=function(root){
if(root===null) return;
dfs(root.left)
dfs(root.right)
result.push(root.val)
}
dfs(root)
return result
};（2）迭代实现
再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：
?
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
if(!root) return []
const res=[],stack=[]
stack.push(root)
while(stack.length){
const cur=stack.pop()
res.push(cur.val)
if(cur.left) stack.push(cur.left)
if(cur.right) stack.push(cur.right)
}
res.reverse()
return res
};四、层次遍历
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if(!root) return []
let res=[],queue=[]
queue.push(root)
while(queue.length){
//当前层个数
let n=queue.length
//存放每一层的节点
let curLevel=[]
//遍历当前层
for(let i=0;i<n;i++){
const cur=queue.shift()
curLevel.push(cur.val)
//把下一层的存进去
if(cur.left) queue.push(cur.left)
if(cur.right) queue.push(cur.right)
}
//把每一层的结果放到结果数组
res.push(curLevel)
}
return res
};