分析
分情况讨论
1、 如果有右孩子,如果有,中继下一个节点是,右子树的最左边的节点
2、 没有右孩子,网上找第一个 p.father.left == p ==>father就是下一个
Code
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = this.father = null;
* }
*/
/**
* @param {TreeNode} p
* @return {TreeNode}
*/
var inorderSuccessor = function(p) {
if(!p) return null;
//case1 有右子树
if(p.right){
p = p.right;
while(p.left){
p = p.left;
}
return p;
}
//case2 没有右子树
while(p.father){
if(p.father.left === p){
return p.father;
}
p = p.father;
}
return null;
};