0°

面试回顾与解析:在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刷题去吧。除了刷题,好像也没啥好办法,谁让你想进大厂呢?

https://juejin.im/post/5ddfe242f265da05b63546bb

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
Keras
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论