理論基礎(chǔ)??
?function TreeNode(val, left, right) {
????this.val = (val===undefined ? 0 : val)
????this.left = (left===undefined ? null : left)
????this.right = (right===undefined ? null : right)
}
二叉樹的三種遞歸遍歷掌握其規(guī)律后譬重，其實(shí)很簡單
前序遍歷：中左右怒坯；
中序遍歷：左中右；
后序遍歷：左右中负甸；
遞歸遍歷??
每次寫遞歸程梦，都按照這三要素來寫罩息，可以保證大家寫出正確的遞歸算法荞胡！
確定遞歸函數(shù)的參數(shù)和返回值：確定哪些參數(shù)是遞歸的過程中需要處理的拼缝，那么就在遞歸函數(shù)里加上這個參數(shù)娱局， 并且還要明確每次遞歸的返回值是什么進(jìn)而確定遞歸函數(shù)的返回類型。
確定終止條件：寫完了遞歸算法, 運(yùn)行的時候咧七，經(jīng)常會遇到棧溢出的錯誤衰齐，就是沒寫終止條件或者終止條件寫的不對，操作系統(tǒng)也是用一個棧的結(jié)構(gòu)來保存每一層遞歸的信息继阻，如果遞歸沒有終止耻涛，操作系統(tǒng)的內(nèi)存棧必然就會溢出废酷。
確定單層遞歸的邏輯：確定每一層遞歸需要處理的信息。在這里也就會重復(fù)調(diào)用自己來實(shí)現(xiàn)遞歸的過程抹缕。
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
迭代遍歷?
統(tǒng)一迭代??
不同于recursion（recursion的本質(zhì)其實(shí)也是stack）澈蟆，迭代直接使用stack進(jìn)行迭代。
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;
};
