题目描述
给定一棵二叉树的其中一个节点,请找出中序遍历序列的下一个节点。
样例
假定二叉树是:[2, 1, 3, null, null, null, null], 给出的是值等于2的节点。
则应返回值等于3的节点。
解释:该二叉树的结构如下,2的后继节点是3。
2
/ \
1 3
假定二叉树是:[1,2,3,4,5,null,null,null,null,null,null,null,null,null,null]
若给出的是值等于4的节点,则应返回值等于2的节点。
若给出的是值等于5的节点,则应返回值等于1的节点。
1
/ \
2 3
/ \
4 5
注意:
如果给定的节点是中序遍历序列的最后一个,则返回空节点;
二叉树一定不为空,且给定的节点一定不是空节点;
C 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* struct TreeNode *father;
* };
*/
struct TreeNode* inorderSuccessor(struct TreeNode* p) {
//左中右
//1.如果当前结点有右子树,则后继结点为右子树中最左下的节点
if (p->right)
{
p = p->right;
while(p->left)
{
p = p->left;//一直往左走,走到左下的位置
}
return p;
}
//2.如果当前结点位于右下方,则后继结点应该往上,直到出现第一个拐点
//3.如果当前结点位于左下方,则后继结点为父节点
while(p->father && p == p->father->right)
{
p = p->father;
}
return p->father;
}