递归
思路很简单，唯一需要记住的就是前中后序的遍历顺序，体现在代码中就是三行代码颠来倒去，其他一摸一样。
前序：根节点 -> 左子树 -> 右子树 中序： 左子树 -> 根节点 -> 右子树 后序：左子树 -> 右子树 -> 根节点
模版
var bTreeRecursion = function(root) {
let res = []
traverse(root)
return res
function traverse(root) {
if(root) {
/*
// 前序
res.push(root.val)
traverse(root.left)
traverse(root.right)
// 中序
traverse(root.left)
res.push(root.val)
traverse(root.right)
// 后序
traverse(root.left)
traverse(root.right)
res.push(root.val)
*/
}
}
};
循环
用数组模拟一个栈，按前中后顺的要求调整出入栈的顺序。值得注意的是，在每一个 root 节点入栈之后，往栈中推入一个 null 节点，是为了给做一个「区隔」，如果遇到出栈的是一个 null，说明下一个出栈的节点需要被推入结果数组了。具体原理跟一遍代码就理解了。
模版
var bTreeLoop = function(root) {
let res = []
let stack = []
if(root){
stack.push(root)
}
while(stack.length) {
root = stack.pop()
if(root) {
/*
//前序
root.right && stack.push(root.right)
root.left && stack.push(root.left)
stack.push(root)
stack.push(null)
//中序
root.right && stack.push(root.right)
stack.push(root)
stack.push(null)
root.left && stack.push(root.left)
//后序
stack.push(root)
stack.push(null)
root.right && stack.push(root.right)
root.left && stack.push(root.left)
*/
} else {
res.push(stack.pop().val)
}
}
return res
};
层次遍历
- 维护一个队列，把节点按层序，顺序入队
- 用 null 节点做层与层之间的区隔。
- 做维护一个当前的层的计数，计数可以用来作为结果数组的 index，
代码看起来和以上循环的逻辑很相似。
代码
var levelOrder = function(root) {
let res = []
let queue = []
let level = 0
if(root) {
queue.push(root, null)
}
while(queue.length) {
let node = queue.shift()
if(node) {
res[level] = res[level] || []
res[level].push(node.val)
node.left && queue.push(node.left)
node.right && queue.push(node.right)
} else {
queue.length && queue.push(null)
level++
}
}
return res
};
leetcode 题目
144. 二叉树的前序遍历(迭代和递归) 94. 二叉树的中序遍历(迭代和递归) 145. 二叉树的后序遍历(迭代和递归) 102. 二叉树的层序遍历 (迭代和递归)
