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

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

必考 算法

練習二叉樹的前序遍曆

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

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

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

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

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

// 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.

[二叉樹的層次遍曆 ??](

)

最後

光給面試題不給答案不是我的風格。這裏面的面試題也只是鳳毛麟角,還有答案的話會極大的增加文章的篇幅,减少文章的可讀性

 CodeChina開源項目:【一線大廠Java面試題解析+核心總結學習筆記+最新講解視頻】

Java面試寶典2021版

大廠首發:必考的算法與數據結構,在字節跳動我是如何當面試官的_後端

大廠首發:必考的算法與數據結構,在字節跳動我是如何當面試官的_後端_02

最常見Java面試題解析(2021最新版)

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

大廠首發:必考的算法與數據結構,在字節跳動我是如何當面試官的_程序員_04

2021企業Java面試題精選

大廠首發:必考的算法與數據結構,在字節跳動我是如何當面試官的_程序員_05

大廠首發:必考的算法與數據結構,在字節跳動我是如何當面試官的_後端_06

版权声明:本文为[Android我愛死你了]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210920044124161e.html