理论基础
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
二叉树的三种递归遍历掌握其规律后，其实很简单
前序遍历：中左右；
中序遍历：左中右；
后序遍历：左右中；
递归遍历
每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！
确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
144.二叉树的前序遍历(opens new window)
preorder traversal
145.二叉树的后序遍历(opens new window)
postorder traversal
const dfs(root) => {
if (root === null) return;
dfs(root.left);
dfs(root.right);
res.push(root.val);
}
inorder traversal
迭代遍历
统一迭代
不同于recursion（recursion的本质其实也是stack），迭代直接使用stack进行迭代。
let stack = [root]
while (stack.length) {
let cur = stack.pop();
if (cur.left) stack.push(cur.left)
if (cur.right) stack.push(cur.right)
res.push(cur.val)
}
在迭代遍历中，中序遍历的写法完全不同于前/后遍历。
var inorderTraversal = function(root) {
let res = []
const stack = [];
let cur = root;
while(stack.length || cur) {
if(cur) {
stack.push(cur);
// 左
cur = cur.left;
} else {
// --> 弹出 中
cur = stack.pop();
res.push(cur.val);
// 右
cur = cur.right;
}
};
return res;
};
