大廠首發：必考的算法與數據結構，在字節跳動我是如何當面試官的

Android我愛死你了 2021-09-20 04:41:24 阅读数:457

必考算法

練習二叉樹的前序遍曆

給你二叉樹的根節點 root ，返回它節點值的前序遍曆。

假設我們mock一下假數據??

那麼根據我們對前序遍曆的理解，我們可以寫出解題偽代碼??

// TianTianUp
// * function TreeNode(val, left, right) {
// * this.val = (val===undefined ? 0 : val)
// * this.left = (left===undefined ? null : left)
// * this.right = (right===undefined ? null : right)
// * }
let preorderTraversal = (root, arr = []) => {
if(root) {
arr.push(root.val)
preorderTraversal(root.left, arr)
preorderTraversal(root.right, arr)
}
return arr
}


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.

非遞歸版本??

對於非遞歸的話，我們需要借助一個數據結構去存儲它的節點，需要使用的就是棧，它的思路可以借鑒??

根節點為目標節點，開始向它子節點遍曆
1.訪問目標節點
2.左孩子入棧 -> 直至左孩子為空的節點
3.節點出棧，以右孩子為目標節點，再依次執行1、2、3

 let preorderTraversal = (root, arr = []) => {
const stack = [], res = []
let current = root
while(current || stack.length > 0) {
while (current) {
res.push(current.val)
stack.push(current)
current = current.left
}
current = stack.pop()
current = current.right
}
return res
}


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.

中序遍曆

給定一個二叉樹，返回它的中序遍曆。

示例:

輸入: [1,null,2,3] 1
2 / 3

輸出: [1,3,2]

進階: 遞歸算法很簡單，你可以通過迭代算法完成嗎？

來源：力扣（LeetCode）著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

遞歸版本??

const inorderTraversal = (root, arr = []) => {
if(root) {
inorderTraversal(root.left, arr)
arr.push(root.val)
inorderTraversal(root.right, arr)
}
return arr
}


1.
2.
3.
4.
5.
6.
7.
8.
9.

非遞歸版本，這裏就不解釋了，跟前序遍曆一樣，思路一樣，用棧維護節點信息。

const inorderTraversal = (root, arr = []) => {
const stack = [], res = []
let current = root
while(current || stack.length > 0) {
while (current) {
stack.push(current)
current = current.left
}
current = stack.pop()
res.push(current.val)
current = current.right
}
return res
}


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.

後續遍曆

給定一個二叉樹，返回它的後序遍曆。

示例:

輸入: [1,null,2,3]
1
2 / 3

輸出: [3,2,1]

進階: 遞歸算法很簡單，你可以通過迭代算法完成嗎？

來源：力扣（LeetCode）著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

遞歸版本??

const postorderTraversal = (root, arr = []) => {
if(root) {
postorderTraversal(root.left, arr)
postorderTraversal(root.right, arr)
arr.push(root.val)
}
return arr
}


1.
2.
3.
4.
5.
6.
7.
8.
9.

非遞歸版本??

其實，嗯，做完前面兩個後，會發現都是有套路滴~

const postorderTraversal = (root, arr = []) => {
const stack = [], res = []
let current = root, last = null // last指針記錄上一個節點
while(current || stack.length > 0) {
while (current) {
stack.push(current)
current = current.left
}
current = stack[stack.length - 1]
if (!current.right || current.right == last) {
current = stack.pop()
res.push(current.val)
last = current
current = null // 繼續彈棧
} else {
current = current.right
}
}
return res
}


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.