二叉树的下一个节点

给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。

注意：

如果给定的节点是中序遍历序列的最后一个，则返回空节点; 二叉树一定不为空，且给定的节点一定不是空节点；

样例 假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。 则应返回值等于3的节点。 解释：该二叉树的结构如下，2的后继节点是3。 2 / \ 1 3

题解

时间复杂度O(h)

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; } }