二叉树的下一个结点

function GetNext(pNode) {
  if(!pNode) {
    return null;
  }
  // 存在右孩子，则返回右子树中最左节点
  if(pNode.right) {
    pNode = pNode.right;
    while(pNode.left) {
      pNode = pNode.left;
    }
    return pNode;
  } else {
    while(pNode) {
      // 中序遍历最后一个节点没有下一个节点
      if(pNode.next===null) {
        return null;
      // 节点是其父亲节点的左孩子，则直接返回其父亲节点
      }else if(pNode === pNode.next.left) { 
        return pNode.next;
      }
      // 节点是其父亲节点的右孩子，往上蹭分析
      pNode = pNode.next;
    }
    return pNode;
  }
}

/*function TreeLinkNode(x){
    this.val = x;
    this.left = null;
    this.right = null;
    this.next = null;
}*/
//暴力解法
let mydata=[]
function GetNext(pNode)
{    
    //传入的第一个节点就是我们要求的节点的父节点 而并不是树的真正根节点
    let firstnode=pNode
    //保存传入的节点
    let temp=pNode
    //递归父树直到根节点 
    while(temp.next!=null){
        temp=temp.next
    }
    //传入真正的根节点 中序遍历保存结果
    getmydata(temp)
    //保存要返回的结果
    let finaldata=null
    //遍历中序树的数组
    mydata.forEach((v,i)=>{
        if(v==firstnode){
                       //返回要求节点的下一个节点 
           finaldata= mydata[i+1]
        }
    })
    
    return finaldata
}
//中序遍历
function getmydata(pNode){
    if(!pNode) return 
    getmydata(pNode.left)
    mydata.push(pNode)
    getmydata(pNode.right)
}

module.exports = {
    GetNext : GetNext
};

    第一种情况，当前节点含有右子树，这种情况下，中序遍历的下一个节点为该节点右子树的最左子节点。因此我们只要从右子节点出发，一直沿着左子节点的指针，就能找到下一个节点。

    第二种情况是，1.当前节点不含有右子树，并且当前节点为父节点的左子节点，这种情况下中序遍历的下一个节点为当前节点的父节点。

    2.当前节点不含有右子树，并且当前节点为父节点的右子节点，这种情况下我们沿着父节点一直向上查找，直到找到一个节点，该节点为父节点的左子节点。这个左子节点的父节点就是中序遍历的下一个节点。

function GetNext(pNode)
{
    // write code here
    if(pNode == null) return null;
    if(pNode.right !== null) { //有右子树 下一个节点就是右子树的 最左边的节点；
        let p = pNode.right;
        while(p.left !== null) {
            p = p.left;
        }
        return p;
    }
    while (pNode.next !== null) { //没有右子树
        if(pNode == pNode.next.left) {
            return pNode.next;
        }
        pNode = pNode. next;
    }
}

function GetNext(pNode)
{
    // write code here
    //1.如果一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点。也就是说，从右子节点出发一直沿着指向左子节点的指针，我们就能找到下一个节点。

    //2.如果没有右子树，又可以分为两种情况
        //1)如果节点是它父节点的左子节点，那么它的下一个节点就是它的父节点。
        //2)如果一个节点既没有右子树，并且它还是父节点的右子节点，那么需要沿着指向父节点的指针一直向上便利，直到找到一个是它父节点的左子节点的节点。
    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 == pNode.next.left) {
            return pNode.next;
        }
        pNode = pNode.next;
    }
    return null;
}

/*1.如果一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点。也就是说，从右子节点出发一直沿着指向左子节点的指针，我们就能找到下一个节点。

2.如果没有右子树，又可以分为两种情况

如果节点是它父节点的左子节点，那么它的下一个节点就是它的父节点。
如果一个节点既没有右子树，并且它还是父节点的右子节点，那么需要沿着指向父节点的指针一直向上遍历，直到找到一个当前节点的父节点的左节点是其本身的节点。
*/
function GetNext(pNode) {
    if (pNode === null) {
        return null;
    }
    if (pNode.right !== null) {
        // 第1种
        pNode = pNode.right;
        while (pNode.left !== null) {
            pNode = pNode.left;
        }
        return pNode;
    }
    while (pNode.next !== null) {
        // 第2种，直到找到一个当前节点的父节点的左节点是其本身的节点。
        if (pNode === pNode.next.left) {
            return pNode.next;
        }
        pNode = pNode.next;
    }
    return null;
}

/*function TreeLinkNode(x){
    this.val = x;
    this.left = null;
    this.right = null;
    this.next = null;
}*/
function GetNext(pNode)
{
    //var p=null;
    if(pNode==null) return pNode;
    if(pNode.right){
        //如果存在右子树
        pNode=pNode.right;//将当前节点转化为原来节点的右子节点，寻找该右子树最左边的节点
        while(pNode.left!=null){
            pNode=pNode.left;
        }
        return pNode
    }
    while(pNode.next!=null){
        //没有右子树,找第一个当前节点是父节点左孩子的节点
        if(pNode==pNode.next.left)
            return pNode.next;
    }
    return null;
    //直到根节点依旧没有找到，返回null
}

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

pNode = pNode.right

3..如果给定的节点（pNode）没有右子节点，就向给定节点的父亲遍历，并判断pNode是否为其父亲的右子节点，若为真，则令

 pNode = pNode.next

直到pNode为其父亲的左子节点，则pNode的父亲为所求。若pNode的父亲为空，则退出循环返回null，就是下图中I节点

/*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 === null){
        let currNode = pNode;
        while(currNode.next){
            if(currNode === currNode.next.left){
                return currNode.next;
            }
            currNode = currNode.next;
        }
        return null;
    }else{
        let currNode = pNode.right;
        while(currNode.left){
            currNode = currNode.left;
        }
        return currNode;
    }
}

• 循环next找到根节点
• 中序遍历存数组
• 遍历数组

function TreeLinkNode(x){
  this.val = x;
  this.left = null;
  this.right = null;
  this.next = null;
}

let arr = [];
function GetNext(pNode)
{
  // write code here
  // 找到根节点
  let r = pNode;
  while (r.next) {
    r = r.next;
  }
  // 此时r为根节点
  // 中序遍历
  inOrderTraverse(r, pNode);
  // console.log(arr);

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === pNode) {
      return arr[i+1];
    }
  }

  // return resNode;
}

function inOrderTraverse(root, target) {
  let r = root;

  r.left && inOrderTraverse(r.left, target);
  if (r.val) {
    arr.push(r);
  }
  r.right && inOrderTraverse(r.right, target);
}

let node1 = new TreeLinkNode(1);
let node2 = new TreeLinkNode(2);
let node3 = new TreeLinkNode(3);
let node4 = new TreeLinkNode(4);
let node5 = new TreeLinkNode(5);
// let node6 = new TreeLinkNode(6);

// node1.left = node2;
// node1.right = node4;

// node2.right = node3;
// node2.next = node1;

// node3.next = node2;

// node4.left = node5;
// node4.right = node6;
// node4.next = node1;

// node5.next = node4;

// node6.next = node4;

// let res = GetNext(node3);

node1.left = node2;
node1.right = node5;

node2.left = node3;
node2.right = node4;

node2.next = node1;
node3.next = node2;
node4.next = node2;
node5.nect = node1;

let res = GetNext(node1);

console.log(res);

	// 判断pNode是否有右子树，pNext为右子树最左的节点
// 如果pNode没有右子树，判断pNode是否有父节点：
//     1、当pNode为父节点的左子树，则pNext为父节点，
//     2、否则沿着父节点向上一直追溯到一个节点是它的父节点的左节点  


function GetNext(pNode)
{
    // write code here
    var pRoot = pNode.next;
    if ( pNode == null) {
        return null
    }
    if ( pNode.right != null) {
        var pRight = pNode.right;
        while ( pRight.left != null ) {
            pRight = pRight.left
        }
        return pRight
    }
    while ( pRoot ) {
        if ( pNode == pRoot.left) {
            return pRoot
        } else {
            pNode = pRoot;
            pRoot = pRoot.next
        }
    }
    return null //必须加上，否则编译不通过，当pNode无有节点和父节点时无法判断
}

    function GetNext(pNode) {
      if (!pNode) {
        return null;
      }
      if (pNode.right) {
        pNode = pNode.right;
        while (pNode.left) {
          pNode = pNode.left;
        }
        return pNode;
      } else {
        while (pNode) {
          if (!pNode.next) {
            return null;
          } else if (pNode == pNode.next.left) {
            return pNode.next;
          }
          pNode = pNode.next;
        }
        return pNode;
      }
    }

    }

function GetNext(pNode)
{
    if(!pNode){return null;}    // 空指针
    var p = null;
    if(pNode.right){            // 存在右子树
        p = pNode.right;
        while(p.left){
            p = p.left;
        }
    }else{                      // 不存在右子树
        p = pNode.next;
        if(pNode.next && pNode.next.right == pNode){
            while(p.next && p.next.right == p){    // 上找所有自己是父的右子的节点
                p = p.next;
            }
            if(p.next == null){    //没有父节点了
                p =  null;
            }else{
                p = p.next;
            }
        }
    }
    return p;
}

/*function TreeLinkNode(x){
    this.val = x;
    this.left = null;
    this.right = null;
    this.next = null;
}*/
function GetNext(pNode)
{
    if(pNode == null){
        return null;
    }
    
    if(pNode.right!=null){
        var pRight = pNode.right;
        while(pRight.left!=null){
            pRight = pRight.left;
        }
        var pNext = pRight;
    }else if(pNode.next!=null){
        var pCurrent = pNode;
        var pParent = pNode.next;
        while(pParent!=null&&pCurrent==pParent.right){
            pCurrent = pParent;
            pParent = pParent.next;
        }
        pNext = pParent;
    }
    return pNext;
}

/*function TreeLinkNode(x){
    this.val = x;
    this.left = null;
    this.right = null;
    this.next = null;//父节点
}

思路：
if(它有右子树){找该右子树的左叶子}
else{//它没有右子树
    if(处于父节点的左子树){下一个节点是父节点}
    else if(处于父节点的右子树){
        if(找到一个处于左子树的祖先节点){则下一个节点就是这个祖先节点}
        esle if(没有处于左子树中的祖先节点){没有下一个节点}
    }
}

*/
function GetNext(pNode)
{
    if(!pNode){
        return null;
    }
    var target=null;
    if(pNode.right){ //存在右子树
        target=pNode.right;
        while(target.left){
            target=target.left;
        }
    }else{//不存在右子树
            var parent=pNode.next;
            var curNode=pNode;
            while(parent!=null && curNode == parent.right){ //父节点不是祖父节点的左节点的话就继续找
                curNode=parent;
                parent=parent.next;
            }
            target=parent;
    }
    return target;
}