回顾

话说，几个月前，那时我刚刚开始找工作，对猎头推的一家跨境电商w**h很感兴趣，大有志在必得的兴致。

猎头和我打过招呼，这家公司算法必考，无奈只有一周时间复习的我，按照自己的猜测，在leetcode上重点的刷了下字符串、动态规划之类的题。

可惜压题失败，真正面试时，面试官考的是二叉树中序后继。唉，当场先是有些失落，接着就是一点小紧张。

回想起来，幸亏面试是通过牛客网做的远程面试，要不这些情绪变化一定落在的面试官眼里。

心神不宁的我，又偏偏遇上了一个较真的面试官，非让我和他说清楚思路再开始写……

当场我是没有完全写出来，但心中确是很不服气，毕竟已经写出大半。于是，面试完又努力了一下，把代码完整的写了出来，发给HR。心想着如果转给面试官看一看，也许还有一线生机，但最终还是跪了……

回顾完了面试过程，下面进入正题。

题目

给一个二叉树，以及一个节点(此节点在二叉树中一定存在)，求该节点的中序遍历后继，如果没有返回null

树节点的定义如下：

type TreeNode struct {
    Val int
    Parent *TreeNode
    Left *TreeNode
    Right *TreeNode
}

思路分析

首先，树的中序遍历是遵循（左）-（根）-（右）的顺序依次输出树的节点。

于是，要想知道当前节点的中序后继是什么，首先要知道当前节点在它的父节点的左侧还是右侧。

如果它是在其父节点的左侧，那就简单了，直接返回它的父节点就好。

如果它是在其父节点的右侧，情况又分为以下两种：

1. 如果它有右侧的子节点，那么下一个节点就是以它右侧子节点为根的子树的最左侧节点。
2. 如果它没有右侧子节点，需要向上回溯它的父节点，然后用这个父节点为新的当前节点，在排除已经访问过的节点的前提下，重复上述的判断过程。

根据这个思路，我写了下面的解法。

解法

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刷题去吧。除了刷题，好像也没啥好办法，谁让你想进大厂呢？

本作品采用《CC 协议》，转载必须注明作者和本文链接