面试回顾与解析:在 O (logN) 时间复杂度下求二叉树中序后继

回顾

话说,几个月前,那时我刚刚开始找工作,对猎头推的一家跨境电商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 协议》,转载必须注明作者和本文链接
讨论数量: 3

您说的是美国拼多多吧哈哈…最近也准备要面这家公司暑期的实习了

1个月前 评论

没那么麻烦,写了几行伪代码,大概就是这样
默认根节点的parent和叶子节点的left或right均为null

function func (node) {
  if (node -> right)
    let node1 = node -> right
    while (node1 -> left)
      node1 = node1 -> left
    return node1
  else
    while (node -> parent && node -> parent -> right === node)
      node = node -> parent
    return node ->parent
}

1个月前 评论

这题不难,是求中序遍历的结果中给定节点的下一个节点么?

4周前 评论

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!