57.二叉树的下一个节点

题目描述：

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

知识点：

• 对中序遍历的理解，我觉得就是一个找规律的数学题
• 指针和树进行了结合

解题思路：

• 这道题给我们一个二叉树的某一个节点，要求我们求其中序遍历的下一个节点

• 首先我们来看一个二叉树中序遍历的图

                               ![二叉树的中序遍历.png](https://cdn.nlark.com/yuque/0/2020/png/2378335/1602374874102-d4bc6945-1d0c-42d4-a502-d9ad1ff347d3.png#align=left&display=inline&height=237&margin=%5Bobject%20Object%5D&name=%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86.png&originHeight=237&originWidth=315&size=4629&status=done&style=none&width=315)

• 我们可以发现的是其每个节点的下一个节点总共有这么几种情况

  1. 2 -> 3,4 -> 5,6 -> 7,8 -> 9 其下一个节点一定为其右节点，或者右节点的左节点，或右节点的左节点的左节点……
  2. 1 -> 2,7 -> 8 其为父节点的左节点
  3. 3 -> 4,5 -> 6 其为父节点父节点的左节点……
• 我们只需要按以上的情况进行判断便好，如果最后都没有返回值返回null便好

解题代码：

function GetNext(pNode)
{
    // write code here
    if(!pNode) return null;
    if(pNode.right) {
        pNode = pNode.right;
        while(pNode.left) {
            pNode = pNode.left;
        }
        return pNode;
    }
    while(pNode.next) {
        let temp = pNode.next;
        if(temp.left === pNode) {
            return temp
        }else {
            pNode = temp;
        }
    }
    return null
}