【算法专栏】二叉树的下一个节点

本系列是《剑指offer》或leetcode的JavaScript版本。

每期1-2个算法，也有可能是一个类别。

文章包括题目、思路以及代码。

如果您对本期有不同或者更好的见解，请后台留言，喜欢请点个好看，谢谢阅读。

题目

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路

中序遍历的顺序 左 – 根 – 右

所以寻找下一个节点的优先级应该反过来 优先级 右 – 根 – 左

• 右节点不为空 – 取右节点的最左侧节点

• 右节点为空 – 如果节点是父亲节的左节点 取父节点

• 右节点为空 – 如果节点是父亲节的右节点 父节点已经被遍历过，再往上层寻找…

• 左节点一定在当前节点之前被遍历过

以下图的二叉树来分析：

中序遍历：CBDAEF

• B – 右节点不为空，下一个节点为右节点D

• C – 右节点为空，C是父节点的左节点，取父节点B

• D – 右节点为空，D是父节点的右节点，再往上蹭分析，B是其父节点的左节点，取B的父节点A

• F – 右节点为空，F是父节点的右节点，没有符合条件的节点，F为遍历的最后一个节点，返回null

代码

考察点

• 二叉树

• 复杂问题拆解