题目描述
给定一棵二叉树的其中一个节点,请找出中序遍历序列的下一个节点。
样例
假定二叉树是:[2, 1, 3, null, null, null, null], 给出的是值等于2的节点。
则应返回值等于3的节点。
解释:该二叉树的结构如下,2的后继节点是3。
2
/ \
1 3
Java代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode father;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode inorderSuccessor(TreeNode p) {
if(p==null)
return null;
//1.如果有右孩子,如果有,中继下一个节点是,右子树的最左边的节点
if(p.right!=null){
p=p.right;
while(p.left!=null)
p=p.left;
return p;
}
//2.如果没有左孩子,找父节点
//如果是父节点的左孩子,父节点就是下一个
while(p.father !=null){
if(p.father.left==p)
return p.father;
p=p.father;
}
return null;
}
}