面试回顾与解析：在O(logN)时间复杂度下求二叉树中序后继
回顾
话说，一多个月前，那时我刚刚开始找工作，对猎头推的一家跨境电商w**h很感兴趣，大有志在必得的兴致。
猎头和我打过招呼，这家公司算法必考，无奈只有一周时间复习的我，按照自己的猜测，在leetcode上重点的刷了下字符串、动态规划之类的题。
可惜压题失败，真正面试时，面试官考的是二叉树中序后继。唉，当场先是有些失落，接着就是一点小紧张。
回想起来，幸亏面试是通过牛客网做的远程面试，要不这些情绪变化一定落在的面试官眼里。
心神不宁的我，又偏偏遇上了一个较真的面试官，非让我和他说清楚思路再开始写……
当场我是没有完全写出来，但心中确是很不服气，毕竟已经写出大半。于是，面试完又努力了一下，把代码完整的写了出来，发给HR。心想着如果转给面试官看一看，也许还有一线生机，但最终还是跪了……
回顾完了面试过程，下面进入正题。
题目
给一个二叉树，以及一个节点(此节点在二叉树中一定存在)，求该节点的中序遍历后继，如果没有返回null
树节点的定义如下：
type TreeNode struct {
Val int
Parent *TreeNode
Left *TreeNode
Right *TreeNode
}
思路分析
首先，树的中序遍历是遵循（左）-（根）-（右）的顺序依次输出树的节点。
于是，要想知道当前节点的中序后继是什么，首先要知道当前节点在它的父节点的左侧还是右侧。
如果它是在其父节点的左侧，那就简单了，直接返回它的父节点就好。
如果它是在其父节点的右侧，情况又分为以下两种：
- 如果它有右侧的子节点，那么下一个节点就是以它右侧子节点为根的子树的最左侧节点。
- 如果它没有右侧子节点，需要向上回溯它的父节点，然后用这个父节点为新的当前节点，在排除已经访问过的节点的前提下，重复上述的判断过程。
根据这个思路，我写了下面的解法。
解法
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
}
当时的测试用例：
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)
}
存在的问题
写文章时，我才发现，这个解法有一个bug，是判断根的节点的下一个节点时，永远都返回nil，这是不对的。
这个坑也是自己挖的，上面的代码在一开始时就计处当前节点回溯到根节点的路径，一方面这不是必须提前全部算好;另一方面，也忽略了当前节点是根节点的边界状态。
改进的解法
其实，改进也很简单，一方面，使用双指针，一个代表当前节点，另一个代表它的父节点，即可以不必提前算出当下节点到根节点的路径; 另一方面，需要对根节点是当前的节点的情况做些特殊处理，让程序“误以为”当前节点在根节点的右侧，这样后面的逻辑就能对得上了。
改进后的代码如下：
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
}
总结
关于面试是否要考纯算法题，一直众说纷纭。
反对者说，工作中大都是写业务代码，哪有需要用到算法的地方，能有机会写个递归就顶天了。
支持者说，算法题可以考查候选人的逻辑能力和编码的严谨性，逻辑能力强、编码严谨的工程师做业务开发也一定不会差呀！
其实，说到底考算法只是企业筛选候选人的一种方式。如果企业品牌在外，根本不差候选人，自然可以大浪淘沙，不求合适，但求最好，算法不行，一律pass。否则的话，还是需要多方面考虑，合适最重要。
从面试者的角度来看，遇到不熟悉算法题也不要慌，一般面试时考察的算法不会太冷门，只要基础扎实，冷静分析，即使做不能完全做出来，也能写出个大概来。至于能不能通过面试，那就不好说啦。
如果真不想在算法题上吃亏，请出门左拐，leetcode刷题去吧。除了刷题，好像也没啥好办法，谁让你想进大厂呢？