题目

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

方法

参考：
详细：https://blog.csdn.net/sbq63683210/article/details/51839408
简洁：https://www.bbsmax.com/A/o75Nvn995W/

思路

根据中序遍历的特点，找一个节点的下一个节点，存在下面三种情况
节点存在右子树，把右子树作为遍历起点，沿着该节点的左子树一直深入，直到叶子节点
节点不存在右子树，判断该节点是否为父节点的左孩子，是则返回父节点作为答案
节点不存在右子树，该节点是父节点的右孩子，以父节点作为遍历起点，重复第二条规则

其实2、3规则可以合并
节点存在右子树，把右子树作为遍历起点，沿着该节点的左子树一直深入，直到叶子节点
节点不存在右子树，以父节点作为遍历起点，一直沿着父节点的路径往上，直到找到某个节点是父节点的左孩子位置，范围该节点 —— 总结：找树状图中向右的拐点

代码

/*function TreeLinkNode(x){
    this.val = x;
    this.left = null;
    this.right = null;
    this.next = null;
}*/
function GetNext (pNode) {
  // write code here
  if (!pNode) return null
  if (pNode.right) {
    let p = pNode.right
    while (p.left) p = p.left
    return p
  } else {
    let p = pNode
    while (p.next && p.next.left !== p) p = p.next
    return p.next
  }
}