给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回
问题
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回
中序遍历访问顺序是:左-根-右,这个中序指的是根在访问顺序的中间。
然后当前遍历到了这个结点,因此说明下一个遍历的结点应该是它的右子树中的某个结点。
于是拿到右子树最下层的左儿子节点即可。
对于没有右子树的情况:
1)当前节点是父节点的左儿子
下一个是父节点
2)当前节点是父节点的右儿子
需要持续判断:
记A为父节点,B为父节点的父节点
1.如果A是B左儿子,则B是下一个要访问的节点
2.如果A是B右儿子,A=B,B=father(B),进行循环判断直到1.满足为止
如果B=NULL时还未满足则返回NULL
/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
*/
class Solution {
public