回顧
話說酬姆，一多個(gè)月前嗜桌，那時(shí)我剛剛開始找工作，對獵頭推的一家跨境電商w**h很感興趣辞色，大有志在必得的興致骨宠。
獵頭和我打過招呼，這家公司算法必考相满，無奈只有一周時(shí)間復(fù)習(xí)的我层亿，按照自己的猜測，在leetcode上重點(diǎn)的刷了下字符串立美、動態(tài)規(guī)劃之類的題匿又。
可惜壓題失敗，真正面試時(shí)建蹄，面試官考的是二叉樹中序后繼碌更。唉裕偿，當(dāng)場先是有些失落，接著就是一點(diǎn)小緊張痛单。
回想起來嘿棘，幸虧面試是通過牛客網(wǎng)做的遠(yuǎn)程面試旭绒，要不這些情緒變化一定落在的面試官眼里鸟妙。
心神不寧的我，又偏偏遇上了一個(gè)較真的面試官快压，非讓我和他說清楚思路再開始寫……
當(dāng)場我是沒有完全寫出來圆仔，但心中確是很不服氣，畢竟已經(jīng)寫出大半蔫劣。于是坪郭，面試完又努力了一下，把代碼完整的寫了出來脉幢，發(fā)給HR歪沃。心想著如果轉(zhuǎn)給面試官看一看，也許還有一線生機(jī)嫌松，但最終還是跪了……
回顧完了面試過程沪曙，下面進(jìn)入正題。
題目
給一個(gè)二叉樹萎羔，以及一個(gè)節(jié)點(diǎn)(此節(jié)點(diǎn)在二叉樹中一定存在)液走，求該節(jié)點(diǎn)的中序遍歷后繼，如果沒有返回null
樹節(jié)點(diǎn)的定義如下：
type TreeNode struct {
Val int
Parent *TreeNode
Left *TreeNode
Right *TreeNode
}
思路分析
首先贾陷，樹的中序遍歷是遵循（左）-（根）-（右）的順序依次輸出樹的節(jié)點(diǎn)缘眶。
于是，要想知道當(dāng)前節(jié)點(diǎn)的中序后繼是什么髓废，首先要知道當(dāng)前節(jié)點(diǎn)在它的父節(jié)點(diǎn)的左側(cè)還是右側(cè)巷懈。
如果它是在其父節(jié)點(diǎn)的左側(cè)，那就簡單了慌洪，直接返回它的父節(jié)點(diǎn)就好顶燕。
如果它是在其父節(jié)點(diǎn)的右側(cè)，情況又分為以下兩種：
- 如果它有右側(cè)的子節(jié)點(diǎn)冈爹，那么下一個(gè)節(jié)點(diǎn)就是以它右側(cè)子節(jié)點(diǎn)為根的子樹的最左側(cè)節(jié)點(diǎn)涌攻。
- 如果它沒有右側(cè)子節(jié)點(diǎn)，需要向上回溯它的父節(jié)點(diǎn)频伤，然后用這個(gè)父節(jié)點(diǎn)為新的當(dāng)前節(jié)點(diǎn)恳谎，在排除已經(jīng)訪問過的節(jié)點(diǎn)的前提下，重復(fù)上述的判斷過程剂买。
根據(jù)這個(gè)思路惠爽，我寫了下面的解法癌蓖。
解法
func FindNext(root, toFind *TreeNode) *TreeNode {
tmpCurr := toFind
paths := []*TreeNode {tmpCurr}
for tmpCurr.Parent != nil{
paths = append(paths, tmpCurr.Parent)
tmpCurr = tmpCurr.Parent
}
tmpCurr = paths[0]
leftRights := []bool{}
for i:=1; i<len(paths); i++{
parent := paths[i]
if parent.Left == tmpCurr{
leftRights = append(leftRights, true)
}else {
leftRights = append(leftRights, false)
}
tmpCurr = parent
}
visitedMap := make(map[*TreeNode]struct{})
tmpCurr = toFind
for i:=0; i<len(leftRights); {
onLeft := leftRights[i]
if onLeft {
return tmpCurr.Parent
} else {
_, visited := visitedMap[tmpCurr.Right]
visitedMap[tmpCurr] = struct{ }{}
if tmpCurr.Right != nil && !visited {
newRoot := tmpCurr.Right
for newRoot.Left != nil{
newRoot = newRoot.Left
}
return newRoot
} else {
tmpCurr = tmpCurr.Parent
i++
}
}
}
return nil
}
當(dāng)時(shí)的測試用例：
func main() {
tn11 := &TreeNode{Val:11}
tn12 := &TreeNode{Val:12}
tn8:= &TreeNode{Val:8, Left: tn11, Right: tn12}
tn11.Parent = tn8
tn12.Parent = tn8
tn5 := &TreeNode{Val:5, Right:tn8}
tn8.Parent = tn5
tn4 := &TreeNode{Val:4}
tn2 := &TreeNode{Val:2, Left:tn4, Right:tn5}
tn4.Parent = tn2
tn5.Parent = tn2
tn9 := &TreeNode{Val:9}
tn6 := &TreeNode{Val:6, Right:tn9}
tn9.Parent = tn6
tn10 := &TreeNode{Val:10}
tn7 := &TreeNode{Val:7, Left:tn10}
tn10.Parent = tn7
tn3 := &TreeNode{Val:3, Left:tn6, Right:tn7}
tn6.Parent = tn3
tn7.Parent = tn3
tn1 := &TreeNode{Val:1, Left:tn2, Right:tn3}
tn2.Parent = tn1
tn3.Parent = tn1
/**樹的樣子如圖
1
/ \
2 3
/ \ / \
4 5 6 7
\ \ /
8 9 10
/ \
11 12
**/
res := FindNext(tn1, tn8)
fmt.Println(res)
res = FindNext(tn1, tn12)
fmt.Println(res)
res = FindNext(tn1, tn9)
fmt.Println(res)
}
存在的問題
寫文章時(shí)，我才發(fā)現(xiàn)婚肆，這個(gè)解法有一個(gè)bug租副，是判斷根的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)時(shí)，永遠(yuǎn)都返回nil较性，這是不對的用僧。
這個(gè)坑也是自己挖的，上面的代碼在一開始時(shí)就計(jì)處當(dāng)前節(jié)點(diǎn)回溯到根節(jié)點(diǎn)的路徑赞咙，一方面這不是必須提前全部算好;另一方面责循，也忽略了當(dāng)前節(jié)點(diǎn)是根節(jié)點(diǎn)的邊界狀態(tài)。
改進(jìn)的解法
其實(shí)攀操，改進(jìn)也很簡單院仿，一方面，使用雙指針速和，一個(gè)代表當(dāng)前節(jié)點(diǎn)歹垫，另一個(gè)代表它的父節(jié)點(diǎn)，即可以不必提前算出當(dāng)下節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑; 另一方面颠放，需要對根節(jié)點(diǎn)是當(dāng)前的節(jié)點(diǎn)的情況做些特殊處理排惨，讓程序“誤以為”當(dāng)前節(jié)點(diǎn)在根節(jié)點(diǎn)的右側(cè)，這樣后面的邏輯就能對得上了碰凶。
改進(jìn)后的代碼如下：
func FindNext(root, toFind *TreeNode) *TreeNode {
tmpCurr := toFind
tmpParent := toFind.Parent
if toFind == root {
tmpParent = root // cheat the parent nil check, and it will go to the right child branch
}
visitedMap := make(map[*TreeNode]struct{})
for tmpParent != nil {
if tmpParent.Left == tmpCurr {
return tmpParent
} else {
_, visited := visitedMap[tmpCurr.Right]
visitedMap[tmpCurr] = struct{ }{}
if tmpCurr.Right != nil && !visited{
tmpCurr = tmpCurr.Right
for tmpCurr.Left != nil {
tmpCurr = tmpCurr.Left
}
return tmpCurr
} else {
tmpCurr = tmpParent
tmpParent = tmpCurr.Parent
}
}
}
return nil
}
總結(jié)
關(guān)于面試是否要考純算法題暮芭，一直眾說紛紜。
反對者說欲低，工作中大都是寫業(yè)務(wù)代碼辕宏，哪有需要用到算法的地方，能有機(jī)會寫個(gè)遞歸就頂天了伸头。
支持者說匾效，算法題可以考查候選人的邏輯能力和編碼的嚴(yán)謹(jǐn)性舷蟀，邏輯能力強(qiáng)恤磷、編碼嚴(yán)謹(jǐn)?shù)墓こ處熥鰳I(yè)務(wù)開發(fā)也一定不會差呀！
其實(shí)野宜，說到底考算法只是企業(yè)篩選候選人的一種方式扫步。如果企業(yè)品牌在外，根本不差候選人匈子，自然可以大浪淘沙河胎，不求合適，但求最好虎敦，算法不行游岳，一律pass政敢。否則的話，還是需要多方面考慮胚迫，合適最重要喷户。
從面試者的角度來看，遇到不熟悉算法題也不要慌访锻，一般面試時(shí)考察的算法不會太冷門褪尝，只要基礎(chǔ)扎實(shí)，冷靜分析期犬，即使做不能完全做出來河哑，也能寫出個(gè)大概來。至于能不能通過面試龟虎，那就不好說啦璃谨。
如果真不想在算法題上吃虧，請出門左拐鲤妥，leetcode刷題去吧睬罗。除了刷題，好像也沒啥好辦法旭斥，誰讓你想進(jìn)大廠呢容达？
