public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
分析如下：
（1）如果一个节点有右子树，则该点的下一个节点为右子树中的最左子节点。
接下来分析一个节点没有右子树的情况，若该节点没有右子树，则：
（1）当该节点是其父节点的左子节点时，那么它的下一个节点就是它的父节点；
（2）当该节点是其父节点的右子节点时，这种情况较为复杂，我们需要沿着父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点（找到的这个节点要是它父节点的左子节点）。如果找不到这样的节点，则当前节点时中序遍历的最后一个节点。
public class Solution { public TreeLinkNode GetNext(TreeLinkNode pNode) { if(pNode == null) return null; // 当前给定节点右子树不为空 if(pNode.right != null){ pNode = pNode.right; while(pNode.left != null){ pNode = pNode.left; } return pNode; } //以下为右子树节点为空的情况 //父节点不为空 while(pNode.next != null) { //如果当前节点为其父节点的子节点，则父节点即为当前节点的下一个节点 if(pNode.next.left == pNode) return pNode.next; pNode = pNode.next; } return null; } }
原文：https://www.cnblogs.com/Aug-20/p/11774140.html